背景

本题加强版在这。

题目描述

有 $m$ 个盒子和 $n$ 个操作，盒子编号为 $0\dots m-1$。第 $i$ 个操作一共会进行 $r_i-l_i+1$ 轮，第 $j$ 轮会在编号为 $(k(j-1+l_i)+b_i)\bmod m$ 的盒子里放 $a_i$ 个球（$j$ 从 $1$ 开始枚举）。

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

输入格式

第一行四个整数 $n,k,m,p$，表示操作个数，两种关于操作参数和选出的盒子个数。
接下来 $n$ 行，第 $i$ 行四个非负整数 $l_i,r_i,b_i,a_i$ 表示一次操作的参数。

输出格式

一个整数表示价值和对 $10^9+7$ 取模的结果。

2 3 5 2
1 3 2 2
2 3 1 1

13

3 89 1000000 4
2 222 19 2
4 66666 1 9
5 114514 8 10

299126098

提示

本题采用捆绑测试。

• Subtask 1（10pts）：$m\le 10^6$;
• Subtask 2（5pts）：$p=1$;
• Subtask 3（30pts）：$n\le 10$，$m\le 10^9$;
• Subtask 4（30pts）：保证 $k$ 和 $m$ 互质;
• Subtask 5（25pts）：无特殊限制。

对于 $100\%$ 的数据，$1\le n\le 7000$，$1\le m\le 10^{18}$，$1\le p\le 4$，$0\le b_i< m$，$0<k<m$，$0\le l_i\le r_i< m$，$0\le a_i<10^9+7$。