Description

请你提交一份代码，使得能够在满足题面描述的情况下通过此题。

Format

Input

本题包含多组测试数据。

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

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

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

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

Output

对于每组测试数据输出一行，包含一个整数，表示方案数对 $10^9 + 7$ 取模的结果。

Samples

3
2 1 2
1 1
2 2 2
1 1
2 2
2 2 2
1 1
1 2

4
3
0

Limitation

【样例 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$		$2$	无
$3$	$9$
$4, 5$	$12$
$6$	$10^3$	$1$	$10^3$
$7$	$10^5$		$10^5$
$8,9$	$10^9$		$10^9$
$10$	$10^3$			A
$11$	$10^4$
$12$	$10^5$
$13$	$10^4$	$10^3$	$10^4$	B
$14$	$10^6$	$10^4$	$10^6$
$15, 16$	$10^9$	$10^5$	$10^9$
$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$。

assign.zip