Description

Xiao F has $n$ variables $x_1, x_2, \ldots, x_n$. Each variable can take integer values from $1$ to $v$.

Xiao F added $n - 1$ binary constraints between these variables. The $i$-th constraint ($1 \leq i \leq n - 1$) is: if $x_i = a_i$, then $x_{i+1} = b_i$ must hold, where $a_i$ and $b_i$ are integers between $1$ and $v$. When $x_i \neq a_i$, the $i$-th constraint imposes no restrictions on $x_{i+1}$. Additionally, Xiao F added $m$ unary constraints, where the $j$-th constraint ($1 \leq j \leq m$) states $x_{c_j} = d_j$.

Xiao F remembers all $c_j$ and $d_j$ values but has forgotten all $a_i$ and $b_i$ values. However, Xiao F knows that there exists an assignment to all variables that satisfies all constraints.

Now, Xiao F wants to determine how many possible combinations of $a_i, b_i$ ($1 \leq i \leq n - 1$) exist such that there is at least one valid assignment satisfying all constraints. Since the number might be large, output the result modulo $10^9 + 7$.

Input Format

The problem contains multiple test cases.

The first line of input contains an integer $T$, the number of test cases.

This is followed by $T$ test cases, each formatted 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 variable values.
• The next $m$ lines each contain two integers $c_j$, $d_j$, describing a unary constraint.

Output Format

For each test case, output one line containing an integer, the number of valid combinations modulo $10^9 + 7$.

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

4
3
0

Hint

Explanation for Sample #1

• First test case: All possible $(a_1, b_1)$ combinations $(1,1)$, $(1,2)$, $(2,1)$, $(2,2)$ are valid. For example:

  • When $(a_1, b_1) = (1,1)$, $(x_1, x_2) = (1,1)$ satisfies all constraints.
  • When $(a_1, b_1) = (2,2)$, both $(x_1, x_2) = (1,1)$ and $(x_1, x_2) = (1,2)$ are valid.

• Second test case: The only valid assignment is $(x_1, x_2) = (1,2)$. Thus:

  • $(a_1, b_1) = (1,1)$ is invalid (requires $x_2=1$), but the other three combinations are valid.

• Third test case: No assignment satisfies both $x_1=1$ and $x_1=2$, so no valid combinations exist.

Sample #2

See files assign/assign2.in and assign/assign2.ans in the problem directory.

This sample contains 10 test cases, where the $i$-th test case ($1 \leq i \leq 10$) satisfies the constraints for test point $i$ in the data range.

Sample #3

See files assign/assign3.in and assign/assign3.ans in the problem directory.

This sample contains 10 test cases, where the $i$-th test case ($1 \leq i \leq 10$) satisfies the constraints for test point $i + 10$ in the data range.

Data Range

For all test data, it is guaranteed that:

• $1 \leq T \leq 10$,
• $1 \leq n \leq 10^9$, $1 \leq m \leq 10^5$, $2 \leq v \leq 10^9$,
• For all $j$ ($1 \leq j \leq m$), $1 \leq c_j \leq n$, $1 \leq d_j \leq v$.

• Special Property A: $m = n$ and $c_j = j$ for all $j$ ($1 \leq j \leq m$).
• Special Property B: $d_j = 1$ for all $j$ ($1 \leq j \leq m$).

Translated by DeepSeek R1