#P17733. [2026年福建省队集训]球盒

[2026年福建省队集训]球盒

题目描述

有 mm 个盒子和 nn 个操作,盒子编号为 0…m−10\dots m-1。第 ii 个操作一共会进行 ri−li+1r_i-l_i+1 轮,第 jj 轮会在编号为 (k(j−1+li)+bi) mod m(k(j-1+l_i)+b_i)\bmod m 的盒子里放 aia_i 个球(jj 从 11 开始枚举)。

在所有操作完成后,小 C 需要选出 pp 个不同的且编号不相邻的盒子,定义一次选择的价值为 pp 个盒子里面球个数的乘积。求所有选择方案的价值和模 109+710^9+7。

输入格式

本题有多组测试数据。

第一行 22 个整数 c,Tc,T,分别表示测试点编号和测试数据组数。c=0c=0 表示该测试点为样例。

接下来依次输入每组测试数据,对于每组测试数据:

第一行四个整数 n,k,m,pn,k,m,p,表示操作个数,两种关于操作参数和选出的盒子个数。

接下来 nn 行,第 ii 行四个非负整数 li,ri,bi,ail_i,r_i,b_i,a_i 表示一次操作的参数。

输出格式

对于每组测试数据,输出一行一个整数表示价值和对 109+710^9+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∼76\sim 7 的约束条件。

样例 3

见选手目录下的 ball/ball3.in 与 ball/ball3.ans。

这个样例满足测试点 8∼108\sim 10 的约束条件。

样例 4

见选手目录下的 ball/ball4.in 与 ball/ball4.ans。

这个样例满足测试点 11∼1211\sim 12 的约束条件。

样例 5

见选手目录下的 ball/ball5.in 与 ball/ball5.ans。

这个样例满足测试点 19∼2019\sim 20 的约束条件。

数据范围

对于 100%100\% 的数据,1≤T≤1001\le T\le 100,1≤n≤70001\le n\le 7000,∑n≤2×104\sum n\le 2\times 10^4,1≤m≤10181\le m\le 10^{18},1≤p≤41\le p\le 4,0≤bi<m0\le b_i< m,0<k<m0<k<m,0≤li≤ri<m0\le l_i\le r_i< m,0≤ai<109+70\le a_i<10^9+7。

测试点编号 nn mm pp 特殊限制
1∼21\sim 2 ≤7000\le 7000 ≤106\le 10^6 ≤4\le 4 T≤5T\le 5
33 ≤1018\le 10^{18} =1=1 无
4∼54\sim 5 ≤10\le 10 ≤109\le 10^9 =2=2
6∼76\sim 7 ≤7000\le 7000 ≤1018\le 10^{18}
8∼108\sim 10 ≤10\le 10 ≤109\le 10^9 =3=3
11∼1211\sim 12 ≤7000\le 7000 ≤1018\le 10^{18} kk 和 mm 互质
13∼1413\sim 14 无
15∼1615\sim 16 ≤10\le 10 ≤109\le 10^{9} =4=4
17∼1817\sim 18 ≤7000\le 7000 ≤1018\le 10^{18} kk 和 mm 互质
19∼2019\sim 20 无