Counting Valid Binary Constraints in a Chain with Unary Fixes

Consider (n) variables (x_1, x_2, \ldots, x_n), each taking an integer value in ([1, v]). There are (n-1) binary constraints and (m) unary constraints. For each (1 \le i \le n-1), the (i)th binary constraint is of the form:

(\text{if } x_i = a_i \text{ then } x_{i+1} = b_i,)

where (a_i, b_i \in {1,2,\ldots,v}). When (x_i \neq a_i), no restriction is imposed on (x_{i+1}).

In addition, there are (m) unary constraints. For each (1 \le j \le m), the constraint is:

(x_{c_j} = d_j,)

with (d_j \in {1,2,\ldots,v}). It is guaranteed that there exists at least one assignment ({x_i}) satisfying all these constraints given the chosen binary constraint parameters ({a_i,b_i}).

Now, having forgotten the values of (a_i) and (b_i), you are asked to count the number of ways to choose (a_i, b_i) (for (1 \le i \le n-1)) such that there is at least one assignment ({x_i}) satisfying all the constraints. Since the answer may be large, output it modulo (10^9+7}.


Observation:
For each binary constraint between (x_i) and (x_{i+1}):

• If both \(x_i\) and \(x_{i+1}\) are fixed (by unary constraints) with values \(d_i\) and \(d_{i+1}\) respectively, then the constraint becomes: if \(d_i = a_i\) then \(b_i\) must be \(d_{i+1}\). This gives \(v\cdot (v-1)+1\) valid choices for \(a_i,b_i\) (\(v-1\) choices for \(a_i\neq d_i\) with any \(b_i\), plus one choice \(a_i=d_i\) with \(b_i=d_{i+1}\)).
• Otherwise (if at least one of \(x_i\) or \(x_{i+1}\) is free), any choice of \(a_i,b_i\) in \([1,v]\) is valid, yielding \(v^2\) possibilities.

Thus, the final answer is the product over \(i=1\) to \(n-1\) of the corresponding factors.

inputFormat

The first line contains three integers \(n\), \(m\), and \(v\) \( (1 \le n \le 10^5, 0 \le m \le n, 1 \le v \le 10^9) \).

Then follow \(m\) lines, each containing two integers \(c_j\) and \(d_j\) \( (1 \le c_j \le n, 1 \le d_j \le v) \), representing the unary constraint \(x_{c_j} = d_j\). It is guaranteed that these constraints are consistent, and there is at least one assignment satisfying all the restrictions.

outputFormat

Output a single integer: the number of valid combinations for the binary constraints \((a_i, b_i)\) modulo \(10^9+7\).

sample

3 2 5
1 2
3 4

625