Xiao Q is a programmer. As a young programmer, Xiao Q is always bullied by Old C, who often assigns troublesome tasks to Xiao Q. Whenever Xiao Q doesn't know how to solve a problem, he turns to you for help.

To complete the task, Xiao Q needs a table. The table has infinitely many rows and infinitely many columns, both indexed starting from 1. To complete the task, every cell in the table is filled with an integer. Xiao Q denotes the integer in the cell at row $a$ and column $b$ as $f(a, b)$. To complete the task, this table must satisfy the following conditions:

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

To complete the task, the table initially contains values such that the value in the cell at row $a$ and column $b$ is $a \times b$. It is clear that this initially satisfies both conditions. To complete the task, Xiao Q needs to perform $m$ modifications to the values in the table. Each time he changes the value of a cell, he must also change all other cells affected by the modification to ensure that the table continues to satisfy both conditions. Xiao Q also needs to ensure that after the modification, the values in all cells remain integers. After completing the modification, he needs to calculate the sum of all values in the first $k$ rows and first $k$ columns. Since the answer can be large, you only need to output the result modulo $1,000,000,007$.

Input

The first line contains two integers $m$ and $n$. There are $m$ operations in total, and all row and column indices involved in the operations do not exceed $n$.

The next $m$ lines each contain four integers $a, b, x, k$, representing that the value at row $a$ and column $b$ is changed to $x$. Then, all cells affected by this change are updated to ensure that all cells remain integers after the modification. After the modification is complete, calculate the sum of all values in the first $k$ rows and first $k$ columns.

Output

Output $m$ lines, each containing the result modulo $1,000,000,007$ after each operation.

Examples

Input 1

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

Output 1

9
36
14

Note 1

Initially, the first 3 rows and 3 columns of the table are as shown on the left. After the first 2 operations, the table remains unchanged. The table after the 3rd operation is shown on the right.

Example 1

Input 2

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

Output 2

2073
316642
12157159
213336861

Constraints

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 < 10^{18}$.