370. 【24NOIP提高组】遗失的赋值(assign) 中等

小 F 有 $n$ 个变量 $x_1$, $x_2$, · · · , $x_n$。每个变量可以取 $1$ 至 $v$ 的整数取值。 小 F 在这 $n$ 个变量之间添加了 $n − 1$ 条二元限制，其中第 $i$($1 ≤ i ≤ n − 1$) 条限制为：若 $x_i = a_i$，则要求 $x_{i+1} = b_i$，且 $a_i$ 与$b_i$ 为$1$ 到$v$ 之间的整数；当 $x_i
eq a_i$ 时，第$i$ 条限制对 $x_{i+1}$ 的值不做任何约束。除此之外，小 F 还添加了 $m$ 条一元限制，其中第$j$($1 ≤ j ≤ m$) 条限制为：$x_{cj} = d_j$。 小 F 记住了所有 $c_j$ 和 $d_j$ 的值，但把所有 $a_i$ 和 $b_i$ 的值都忘了。同时小 F 知道：存在给每一个变量赋值的方案同时满足所有这些限制。 现在小 F 想知道，有多少种 $a_i, b_i$ ($1 ≤ i ≤ n − 1$) 取值的组合，使得能够确保至少存在一种给每个变量 $x_i$ 赋值的方案可以同时满足所有限制。由于方案数可能很大，小F 只需要你输出方案数对 $10^9 + 7$ 取模的结果