Little F has $n$ variables $x_1, x_2, \dots, x_n$. Each variable can take an integer value from $1$ to $v$.

Little F has added $n-1$ binary constraints between these $n$ variables, where the $i$-th ($1 \le i \le n-1$) constraint is: if $x_i = a_i$, then $x_{i+1} = b_i$, where $a_i$ and $b_i$ are integers between $1$ and $v$. When $x_i \neq a_i$, the $i$-th constraint imposes no restriction on the value of $x_{i+1}$. In addition, Little F has added $m$ unary constraints, where the $j$-th ($1 \le j \le m$) constraint is: $x_{c_j} = d_j$.

Little F remembers all the values of $c_j$ and $d_j$, but has forgotten all the values of $a_i$ and $b_i$. At the same time, Little F knows that there exists at least one assignment of values to every variable that satisfies all these constraints simultaneously.

Now, Little F wants to know how many combinations of values for $a_i, b_i$ ($1 \le i \le n-1$) exist such that it is guaranteed that there is at least one assignment of values to every variable $x_i$ that satisfies all constraints simultaneously. Since the number of combinations can be very large, Little F only needs you to output the result modulo $10^9 + 7$.

Input

The input is read from the file assign.in.

This problem contains multiple test cases. The first line contains an integer $T$, representing the number of test cases. The following contains $T$ test cases, and the format for each test case is as follows: The first line contains three integers $n, m, v$, representing the number of variables, the number of unary constraints, and the upper bound of the variable values, respectively. The next $m$ lines each contain two integers $c_j, d_j$, describing a unary constraint.

Output

The output is written to the file assign.out. For each test case, output a single line containing an integer representing the number of combinations modulo $10^9 + 7$.

Examples

Input 1

3
2 1 2
3 1 1
4 2 2
5 1 1
6 2 2
7 2 2
8 1 1
9 1 2

Output 1

4
3
0

Note

• For the first test case, all possible combinations of $(a_1, b_1)$ values $(1, 1), (1, 2), (2, 1), (2, 2)$ satisfy the constraints. For example, when $(a_1, b_1) = (1, 1)$, $(x_1, x_2) = (1, 1)$ satisfies all constraints, and when $(a_1, b_1) = (2, 2)$, both $(x_1, x_2) = (1, 1)$ and $(x_1, x_2) = (1, 2)$ satisfy all constraints.
• For the second test case, there is only one possible variable assignment $(x_1, x_2) = (1, 2)$, so only $(a_1, b_1) = (1, 1)$ does not satisfy the constraints, while the other three assignments do.
• For the third test case, there is no variable assignment that satisfies both $x_1 = 1$ and $x_1 = 2$ simultaneously, so there are no $(a_1, b_1)$ that satisfy the constraints.

Input 2

See assign/assign2.in and assign/assign2.ans in the contestant directory. This example contains 10 test cases, where the $i$-th ($1 \le i \le 10$) test case satisfies the constraints described for test point $i$ in the data range.

Input 3

See assign/assign3.in and assign/assign3.ans in the contestant directory. This example contains 10 test cases, where the $i$-th ($1 \le i \le 10$) test case satisfies the constraints described for test point $i+10$ in the data range.

Constraints

For all test cases, it is guaranteed that: $1 \le T \le 10$ $1 \le n \le 10^9, 1 \le m \le 10^5, 2 \le v \le 10^9$ * For any $j$ ($1 \le j \le m$), $1 \le c_j \le n, 1 \le d_j \le v$

Special Property A: Guaranteed $m = n$, and for any $j$ ($1 \le j \le m$), $c_j = j$. Special Property B: Guaranteed $d_j = 1$.