题目描述
有 m 个盒子和 n 个操作,盒子编号为 0…m−1。第 i 个操作一共会进行 ri−li+1 轮,第 j 轮会在编号为 (k(j−1+li)+bi)modm 的盒子里放 ai 个球(j 从 1 开始枚举)。
在所有操作完成后,小 C 需要选出 p 个不同的且编号不相邻的盒子,定义一次选择的价值为 p 个盒子里面球个数的乘积。求所有选择方案的价值和模 109+7。
输入格式
本题有多组测试数据。
第一行 2 个整数 c,T,分别表示测试点编号和测试数据组数。c=0 表示该测试点为样例。
接下来依次输入每组测试数据,对于每组测试数据:
第一行四个整数 n,k,m,p,表示操作个数,两种关于操作参数和选出的盒子个数。
接下来 n 行,第 i 行四个非负整数 li,ri,bi,ai 表示一次操作的参数。
输出格式
对于每组测试数据,输出一行一个整数表示价值和对 109+7 取模的结果。
样例
样例输入 1
0 2
2 3 5 2
1 3 2 2
2 3 1 1
3 89 1000000 4
2 222 19 2
4 66666 1 9
5 114514 8 10
样例输出 1
13
299126098
样例 2
见选手目录下的 ball/ball2.in 与 ball/ball2.ans。
这个样例满足测试点 6∼7 的约束条件。
样例 3
见选手目录下的 ball/ball3.in 与 ball/ball3.ans。
这个样例满足测试点 8∼10 的约束条件。
样例 4
见选手目录下的 ball/ball4.in 与 ball/ball4.ans。
这个样例满足测试点 11∼12 的约束条件。
样例 5
见选手目录下的 ball/ball5.in 与 ball/ball5.ans。
这个样例满足测试点 19∼20 的约束条件。
数据范围
对于 100% 的数据,1≤T≤100,1≤n≤7000,∑n≤2×104,1≤m≤1018,1≤p≤4,0≤bi<m,0<k<m,0≤li≤ri<m,0≤ai<109+7。
| 测试点编号 |
n |
m |
p |
特殊限制 |
| 1∼2 |
≤7000 |
≤106 |
≤4 |
T≤5 |
| 3 |
≤1018 |
=1 |
无 |
| 4∼5 |
≤10 |
≤109 |
=2 |
| 6∼7 |
≤7000 |
≤1018 |
| 8∼10 |
≤10 |
≤109 |
=3 |
| 11∼12 |
≤7000 |
≤1018 |
k 和 m 互质 |
| 13∼14 |
无 |
| 15∼16 |
≤10 |
≤109 |
=4 |
| 17∼18 |
≤7000 |
≤1018 |
k 和 m 互质 |
| 19∼20 |
无 |