#NOIP2024B. 遗失的赋值(assign)民间数据

遗失的赋值(assign)民间数据

[NOIP2024] 遗失的赋值(民间数据)

题目背景

1s 512MB

题目描述

小 F 有 nn 个变量 x1,x2,,xnx_1, x_2, \ldots , x_n。每个变量可以取 11vv 的整数取值。

小 F 在这 nn 个变量之间添加了 n1n - 1 条二元限制,其中第 ii1in11 \leq i \leq n - 1)条限制为:若 xi=aix_i = a_i,则要求 xi+1=bix_{i+1} = b_iaia_ibib_i11vv 之间的整数;当 xiaix_i \neq a_i 时,第 ii 条限制对 xi+1x_{i+1} 的值不做任何约束。除此之外,小 F 还添加了 mm 条一元限制,其中第 jj1jm1 \leq j \leq m)条限制为:xcj=djx_{c_j} = d_j

小 F 记住了所有 cjc_jdjd_j 的值,但把所有 aia_ibib_i 的值都忘了。同时小 F 知道:存在给每一个变量赋值的方案同时满足所有这些限制。

现在小 F 想知道,有多少种 ai,bia_i, b_i1in11 \leq i \leq n - 1)取值的组合,使得能够确保至少存在一种给每个变量 xix_i 赋值的方案可以同时满足所有限制。由于方案数可能很大,小 F 只需要你输出方案数对 109+710^9 + 7 取模的结果。

输入格式

本题包含多组测试数据

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

接下来包含 TT 组数据,每组数据的格式如下:

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

接下来 mm 行,第 jj 行包含两个整数 cj,djc_j, d_j,描述一个一元限制。

输出格式

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

样例 #1

样例输入 #1

3
2 1 2
1 1
2 2 2
1 1
2 2
2 2 2
1 1
1 2

样例输出 #1

4
3
0

提示

【样例 1 解释】

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

【样例 2】

见选手目录下的 assign/assign2.inassign/assign2.ans

该样例共有 1010 组测试数据,其中第 ii1i101 \leq i \leq 10)组测试数据满足数据范围中描述的测试点 ii 的限制。

【样例 3】

见选手目录下的 assign/assign3.inassign/assign3.ans

该样例共有 1010 组测试数据,其中第 ii1i101 \leq i \leq 10)组测试数据满足数据范围中描述的测试点 i+10i + 10 的限制。

【数据范围】

对于所有的测试数据,保证:

  • 1T101 \leq T \leq 10
  • 1n1091 \leq n \leq 10^91m1051 \leq m \leq 10^52v1092 \leq v \leq 10^9
  • 对于任意的 jj1jm1 \leq j \leq m),都有 1cjn1 \leq c_j \leq n1djv1 \leq d_j \leq v
测试点 nn \leq mm \leq vv \leq 特殊性质
1,21, 2 66 22
33 99
4,54, 5 1212
66 10310^3 11 10310^3
77 10510^5 10510^5
8,98,9 10910^9 10910^9
1010 10310^3 A
1111 10410^4
1212 10510^5
1313 10410^4 10310^3 10410^4 B
1414 10610^6 10410^4 10610^6
15,1615, 16 10910^9 10510^5 10910^9
1717 10410^4 10310^3 10410^4
1818 10610^6 10410^4 10610^6
19,2019, 20 10910^9 10510^5 10910^9

特殊性质 A:保证 m=nm = n,且对于任意的 jj1jm1 \leq j \leq m),都有 cj=jc_j = j

特殊性质 B:保证 dj=1d_j = 1