Problem Description

Xiao Q is a programmer.

As a young programmer, Xiao Q is often bullied by Lao C, who frequently assigns troublesome tasks to Xiao Q. Whenever Xiao Q doesn't know how to solve these tasks, he has to seek your help.

To complete the task, Xiao Q needs to create a table with an infinite number of rows and columns, both numbered starting from 1. Each cell in the table is filled with an integer, and for convenience, Xiao Q denotes the integer in the $a$-th row and $b$-th column as $f(a, b)$. To fulfill the task, the table must satisfy the following conditions:

1. For any positive integers $a, b$, it must hold that $f(a, b) = f(b, a)$;
2. For any positive integers $a, b$, it must hold that $b \times f(a, a + b) = (a + b) \times f(a, b)$.

Initially, the numbers in the table are very regular, with the number in the $a$-th row and $b$-th column being exactly $a \times b$, which clearly satisfies the above two conditions. To complete the task, Xiao Q needs to continuously modify the numbers in the table. Each time a cell is modified, Xiao Q must also update all the cells affected by this change to ensure the table continues to satisfy the above conditions. Due to some magical force, it is guaranteed that all numbers in the table remain integers after each modification. Additionally, Xiao Q needs to frequently obtain the sum of all numbers in the top $k$ rows and $k$ columns, and since the answer can be very large, it should be calculated modulo $1,000,000,007$.

Input Format

The first line of the input file contains two integers $m, n$, indicating that there are $m$ operations, and all operations and queries involve row and column numbers not exceeding $n$.

The next $m$ lines each contain four integers $a, b, x, k$, indicating that the number in the $a$-th row and $b$-th column is changed to $x$, and all affected cells are updated accordingly. After the modification, the sum of all numbers in the top $k$ rows and $k$ columns is calculated.

Output Format

The output consists of $m$ lines, with each line corresponding to the result of an operation, representing the sum modulo $1,000,000,007$.

Sample Input and Output

Input Sample #1

3 3
1 1 1 2
2 2 4 3
1 2 4 2

Output Sample #1

9
36
14

Input Sample #2

4 125
1 2 4 8
1 3 9 27
1 4 16 64
1 5 25 125

Output Sample #2

2073
316642
12157159
213336861

Notes

[Sample Explanation #1]

Initially, the top $3$ rows and $3$ columns of the table are shown on the left. After the first two operations, the table remains unchanged. The table after the third operation is shown on the right.

1 2 3     2  4  6
2 4 6     4  4 12
3 6 9     6 12  9

[Data Range]

For $100\%$ of the test cases, $1 \le m \le 10^4$, $1 \le a, b, k \le n \le 4 \times 10^6$, $0 \le x \le 10^{18}$.

见题面 Input 部分

见题面 Output 部分