题目描述

小 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\neq 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$ 取模的结果

输入

本题包含多组测试数据。 输入的第一行包含一个整数 $T$，表示测试数据的组数。 接下来包含 $T$ 组数据，每组数据的格式如下： 第一行包含三个整数 $n$, $m$, $v$，分别表示变量个数、一元限制个数和变量的取值上限。 接下来 $m$ 行，第 $j$ 行包含两个整数 $c_j$, $d_j$，描述一个一元限制。

输出

对于每组测试数据输出一行，包含一个整数，表示方案数对 $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

提示

【样例 1 解释】 • 对于第一组测试数据，所有可能的 ($a_1$, $b_1$) 取值的组合 ($1$, $1$),($1$, $2$),($2$, $1$),($2$, $2$) 都满足限制。例如，($a_1$, $b_1$) = ($1$, $1$) 时，($x_1$, $x_2$) = ($1$, $1$) 满足所有限制，而 ($a_1$, $b_1$) =($2$, $2$) 时，($x_1$, $x_2$) = ($1$, $1$) 与 ($x_1$, $x_2$) = ($1$, $2$) 均满足所有限制。 • 对于第二组测试数据，只有 ($x_1$, $x_2$) = ($1$, $2$) 一种可能的变量赋值，因此只有($a_1$, $b_1$) = ($1$, $1$) 不满足限制，其余三种赋值均满足限制。 • 对于第三组测试数据，不存在一种变量赋值同时满足 $x_1 = 1$ 和 $x_1 = 2$，因此也不存在满足限制的 ($a_1$, $b_1$)。

测试点	n ≤	m ≤	v ≤	特殊性质
1, 2	6	6	2	无
3	9	9
4, 5	12	12
6	103	1	103
7	105		105
8, 9	109		109
10	103	103	103	A
11	104	104	104
12	105	105	105
13	104	103	104	B
14	106	104	106
15, 16	109	105	109
17	104	103	104	无
18	106	104	106
19, 20	109	105	109

特殊性质 A：保证 $m = n$，且对于任意的 $j$($1 ≤ j ≤ m$)，都有 $c_j = j$。 特殊性质 B：保证 $d_j = 1$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。