Background

The enhanced version of this problem is here.

Problem Description

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$.

Input Format

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 Format

Output one integer, which is the sum of values modulo $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

Hint

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