P8159 "PMOI-5" An Easy Problem That Cannot Prevent an AK.

The enhanced version of this problem is [here](https://www.luogu.com.cn/problem/U203487).

There are $m$ boxes and $n$ operations. The boxes are numbered from $0 \dots m-1$. The $i$-th operation will run for a total of $r_i - l_i + 1$ rounds. In the $j$-th round, $a_i$ balls are put into the box numbered $(k(j-1+l_i)+b_i)\bmod m$ (where $j$ is enumerated starting from $1$). After all operations are completed, you need to choose $p$ different boxes such that no two chosen boxes have adjacent indices. Define the value of one selection as the product of the numbers of balls in these $p$ boxes. Find the sum of the values of all valid selections modulo $10^9+7$.

The first line contains four integers $n, k, m, p$, representing the number of operations, the two parameters related to the operations, and the number of boxes to be chosen. The next $n$ lines each contain four non-negative integers $l_i, r_i, b_i, a_i$, describing the parameters of an operation.

Output one integer, which is the sum of values modulo $10^9+7$.

**This problem uses bundled testdata.** - Subtask 1 (10 pts): $m \le 10^6$. - Subtask 2 (5 pts): $p = 1$. - Subtask 3 (30 pts): $n \le 10$, $m \le 10^9$. - Subtask 4 (30 pts): $k$ and $m$ are coprime. - Subtask 5 (25 pts): No special constraints. For $100\%$ of the testdata, $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$, and $0 \le a_i < 10^9+7$. Translated by ChatGPT 5