OIer博客

小 F 有 $n$ 个变量 $x_1, x_2, \ldots , x_n$。每个变量可以取 $1$ 至 $v$ 的整数取值。

小 F 在这 $n$ 个变量之间添加了 $n – 1$ 条二元限制，其中第 $i$（$1 \leq i \leq n – 1$）条限制为：若 $x_i = a_i$，则要求 $x_{i+1} = b_i$，**且 $a_i$ 与 $b_i$ 为 $1$ 到 $v$ 之间的整数**；当 $x_i \neq a_i$ 时，第 $i$ 条限制对 $x_{i+1}$ 的值不做任何约束。除此之外，小 F 还添加了 $m$ 条一元限制，其中第 $j$（$1 \leq j \leq m$）条限制为：$x_{c_j} = d_j$。

小 F 记住了所有 $c_j$ 和 $d_j$ 的值，但把所有 $a_i$ 和 $b_i$ 的值都忘了。同时小 F 知道：存在给每一个变量赋值的方案同时满足所有这些限制。

现在小 F 想知道，有多少种 $a_i, b_i$（$1 \leq i \leq n – 1$）取值的组合，使得能够确保至少存在一种给每个变量 $x_i$ 赋值的方案可以同时满足所有限制。由于方案数可能很大，小 F 只需要你输出方案数对 $10^9 + 7$ 取模的结果。

**本题包含多组测试数据**。

输入的第一行包含一个整数 $T$，表示测试数据的组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含三个整数 $n, m, v$，分别表示变量个数、一元限制个数和变量的取值上限。

接下来 $m$ 行，第 $j$ 行包含两个整数 $c_j, d_j$，描述一个一元限制。

**【样例 1 解释】**

– 对于第一组测试数据，所有可能的 $(a_1, b_1)$ 取值的组合 $(1, 1), (1, 2), (2, 1), (2, 2)$ 都满足限制。例如，$(a_1, b_1) = (1, 1)$ 时，$(x_1, x_2) = (1, 1)$ 满足所有限制，而 $(a_1, b_1) = (2, 2)$ 时，$(x_1, x_2) = (1, 1)$ 与 $(x_1, x_2) = (1, 2)$ 均满足所有限制。
– 对于第二组测试数据，只有 $(x_1, x_2) = (1, 2)$ 一种可能的变量赋值，因此只有 $(a_1, b_1) = (1, 1)$ 不满足限制，其余三种赋值均满足限制。
– 对于第三组测试数据，不存在一种变量赋值同时满足 $x_1 = 1$ 和 $x_1 = 2$，因此也不存在满足限制的 $(a_1, b_1)$。

**【样例 2】**

见选手目录下的 `assign/assign2.in` 与 `assign/assign2.ans`。

该样例共有 $10$ 组测试数据，其中第 $i$（$1 \leq i \leq 10$）组测试数据满足数据范围中描述的测试点 $i$ 的限制。

**【样例 3】**

见选手目录下的 `assign/assign3.in` 与 `assign/assign3.ans`。

该样例共有 $10$ 组测试数据，其中第 $i$（$1 \leq i \leq 10$）组测试数据满足数据范围中描述的测试点 $i + 10$ 的限制。

**【数据范围】**

对于所有的测试数据，保证：

– $1 \leq T \leq 10$，
– $1 \leq n \leq 10^9$，$1 \leq m \leq 10^5$，$2 \leq v \leq 10^9$，
– 对于任意的 $j$（$1 \leq j \leq m$），都有 $1 \leq c_j \leq n$，$1 \leq d_j \leq v$。

| 测试点 | $n \leq$ | $m \leq$ | $v \leq$ | 特殊性质 |
| :———-: | :———-: | :———-: | :———-: | :———-: |
| $1, 2$ | $6$ | $6$ | $2$ | 无 |
| $3$ | $9$ | $9$ | $2$ | 无 |
| $4, 5$ | $12$ | $12$ | $2$ | 无 |
| $6$ | $10^3$ | $1$ | $10^3$ | 无 |
| $7$ | $10^5$ | $1$ | $10^5$ | 无 |
| $8,9$ | $10^9$ | $1$ | $10^9$ | 无 |
| $10$ | $10^3$ | $10^3$ | $10^3$ | A |
| $11$ | $10^4$ | $10^4$ | $10^4$ | A |
| $12$ | $10^5$ | $10^5$ | $10^5$ | A |
| $13$ | $10^4$ | $10^3$ | $10^4$ | B |
| $14$ | $10^6$ | $10^4$ | $10^6$ | B |
| $15, 16$ | $10^9$ | $10^5$ | $10^9$ | B |
| $17$ | $10^4$ | $10^3$ | $10^4$ | 无 |
| $18$ | $10^6$ | $10^4$ | $10^6$ | 无 |
| $19, 20$ | $10^9$ | $10^5$ | $10^9$ | 无 |

特殊性质 A：保证 $m = n$，且对于任意的 $j$（$1 \leq j \leq m$），都有 $c_j = j$。

特殊性质 B：保证 $d_j = 1$。