小 F 有 n 个变量 x1​,x2​,…,xn​。每个变量可以取 1 至 v 的整数取值。

小 F 在这 n 个变量之间添加了 n−1 条二元限制，其中第 i（1≤i≤n−1）条限制为：若 xi​=ai​，则要求 xi+1​=bi​，且 ai​ 与 bi​ 为 1 到 v 之间的整数；当 xi​=ai​ 时，第 i 条限制对 xi+1​ 的值不做任何约束。除此之外，小 F 还添加了 m 条一元限制，其中第 j（1≤j≤m）条限制为：xcj​​=dj​。

小 F 记住了所有 cj​ 和 dj​ 的值，但把所有 ai​ 和 bi​ 的值都忘了。同时小 F 知道：存在给每一个变量赋值的方案同时满足所有这些限制。

现在小 F 想知道，有多少种 ai​,bi​（1≤i≤n−1）取值的组合，使得能够确保至少存在一种给每个变量 xi​ 赋值的方案可以同时满足所有限制。由于方案数可能很大，小 F 只需要你输出方案数对 109+7 取模的结果。

本题包含多组测试数据。

输入的第一行包含一个整数 T，表示测试数据的组数。

接下来包含 T 组数据，每组数据的格式如下：

第一行包含三个整数 n,m,v，分别表示变量个数、一元限制个数和变量的取值上限。

接下来 m 行，第 j 行包含两个整数 cj​,dj​，描述一个一元限制。

对于每组测试数据输出一行，包含一个整数，表示方案数对 109+7 取模的结果。

【样例 1 解释】

• 对于第一组测试数据，所有可能的 (a1,b1) 取值的组合 (1,1),(1,2),(2,1),(2,2) 都满足限制。例如，(a1,b1)=(1,1) 时，(x1,x2)=(1,1) 满足所有限制，而 (a1,b1)=(2,2) 时，(x1,x2)=(1,1) 与 (x1,x2)=(1,2) 均满足所有限制。
• 对于第二组测试数据，只有 (x1,x2)=(1,2) 一种可能的变量赋值，因此只有 (a1,b1)=(1,1) 不满足限制，其余三种赋值均满足限制。
• 对于第三组测试数据，不存在一种变量赋值同时满足 x1=1 和 x1=2，因此也不存在满足限制的 (a1,b1)。

【样例 2】

见选手目录下的 assign/assign2.in 与 assign/assign2.ans。

该样例共有 10 组测试数据，其中第 i（1≤i≤10）组测试数据满足数据范围中描述的测试点 i 的限制。

【样例 3】

见选手目录下的 assign/assign3.in 与 assign/assign3.ans。

该样例共有 10 组测试数据，其中第 i（1≤i≤10）组测试数据满足数据范围中描述的测试点 i+10 的限制。

【数据范围】

对于所有的测试数据，保证：

• 1≤T≤10，
• 1≤n≤109，1≤m≤105，2≤v≤109，
• 对于任意的 j（1≤j≤m），都有 1≤cj≤n，1≤dj≤v。

特殊性质 A：保证 m=n，且对于任意的 j（1≤j≤m），都有 cj=j。

特殊性质 B：保证 dj=1。