P11362 [NOIP2024] The Lost Assignment

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$.

**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.

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

### 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$. | Test Case | $n \leq$ | $m \leq$ | $v \leq$ | Special Property | | :-------: | :------: | :------: | :------: | :--------------: | | 1, 2 | 6 | 6 | 2 | None | | 3 | 9 | 9 | 2 | None | | 4, 5 | 12 | 12 | 2 | None | | 6 | $10^3$ | 1 | $10^3$ | None | | 7 | $10^5$ | 1 | $10^5$ | None | | 8, 9 | $10^9$ | 1 | $10^9$ | None | | 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$ | None | | 18 | $10^6$ | $10^4$ | $10^6$ | None | | 19, 20 | $10^9$ | $10^5$ | $10^9$ | None | - **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