Non-Adjacent Box Selection

You are given m boxes (numbered from 0 to m-1) and n operations. In the i^th operation, you perform r_i - l_i + 1 rounds. In the j^th round (where j is enumerated starting from 1), you add a_i balls to the box with index

\( (k (j-1+l_i) + b_i) \bmod m \)

After all operations, you need to choose exactly p distinct boxes such that no two chosen boxes have consecutive indices. The "value" of a selection is defined as the product of the numbers of balls in the chosen boxes. Compute the sum of the values of all possible selections modulo \(10^9+7\).

inputFormat

The first line contains four integers: m, n, p and k (m - number of boxes, n - number of operations, p - number of boxes to select, and k as described in the formula).

Then n lines follow, each containing four integers: l_i, r_i, a_i, and b_i, describing the i^th operation.

outputFormat

Output a single integer, which is the sum of the values of all valid selections modulo \(10^9+7\).

sample

3 1 2 1
0 1 2 0

0