Propagated Table Modifications

Little Q is a programmer who is always assigned troublesome tasks by Old C. In one such task, Little Q is given an infinite table with rows and columns indexed from \(1\). Each cell \((a,b)\) contains an integer \(f(a,b)\). The table satisfies the following conditions for all positive integers \(a,b\):

1. \(f(a,b) = f(b,a)\) (symmetry).
2. \(b\, f(a,a+b) = (a+b)\, f(a,b)\).

Initially the table is filled with \(f(a,b) = a \times b\), which satisfies the conditions. However, Little Q is allowed to modify some cell values. When he modifies a cell \((r,c)\) to a new value \(V\), the magic of the table forces all the affected cells to change so that the table continues to satisfy the above conditions. It can be proven that after every modification, every cell in the table is still an integer.

In fact, one may show that the two conditions force the function \(f(a,b)\) to be of the form

[ f(a,b) = a \times b \times X(\gcd(a,b)) ]

for some function \(X: \mathbb{N}^+ \to \mathbb{Z}\). Initially, \(X(n)=1\) for all \(n\). When a cell at \((r,c)\) is modified to \(V\), let \(d=\gcd(r,c)\); then to keep the table consistent we must have

[ V = r \times c \times X(d) \quad \Longrightarrow \quad X(d) = \frac{V}{r, c}. ]

Little Q is also required to answer queries. Given an integer \(k\), compute the sum of the numbers in the subtable of the first \(k\) rows and first \(k\) columns, i.e.,

[ S(k) = \sum_{1 \le i,j \le k} f(i,j) \mod 1,000,000,007. ]

You are given \(T\) operations. Each operation is one of the following types:

• Update: 1 r c V meaning that cell \((r,c)\) is changed to \(V\), causing \(X(\gcd(r,c))\) to be updated to \(V/(r\,c)\).
• Query: 2 k asking for the value of \(S(k)\) modulo \(1\,000\,000\,007\).

Note: It is guaranteed that after every update the value \(V/(r\,c)\) is an integer.

inputFormat

The first line contains an integer \(T\) \((1 \le T \le \text{small})\), the number of operations.

Each of the next \(T\) lines represents an operation in one of the following two formats:

• 1 r c V — An update operation. \(r\), \(c\) and \(V\) are positive integers. It sets the cell \((r,c)\) to \(V\) and updates \(X(\gcd(r,c)) = V/(r\,c)\).
• 2 k — A query operation. \(k\) is a positive integer. You need to output \(S(k) = \sum_{i=1}^{k}\sum_{j=1}^{k} f(i,j) \mod 1\,000\,000\,007\).

You can assume that all numbers in the input are such that the required operations can be performed within time limits.

outputFormat

For every query operation, output the corresponding value of \(S(k)\) in a separate line.

sample

3
2 3
1 2 3 30
2 3

36
128

</p>