Akash is interested in a new function F such that,

\(F(x) = \frac{1}{GCD(1, x)} + \frac{2}{GCD(2, x)} + ... + \frac{x}{GCD(x, x)}\)

where \(GCD\) is the Greatest Common Divisor.

Now, the problem is quite simple. Given an array A of size N, there are 2 types of queries:

C X Y : Compute the value of \(F(A[X] ) + F(A[X + 1]) + F(A[X + 2]) + .... + F( A[Y] ) \) (mod\( 10^9 + 7\))
U X Y: Update the element of array \(A[X] = Y\)

Input:
First line of input contain integer N, size of the array.
Next line contain N space separated integers. Next line contain integer Q, number of queries.
Next Q lines contain one of the two queries.

Output:
For each of the first type of query, output the required sum (mod \(10^9 + 7\)).

Constraints:
\(1 \le N \le 10^6\)
\(1 \le Q \le 10^5\)
\(1 \le A[i] \le 5 * 10^5\)
For \(1^{st}\) type of query,
\(1 \le X \le Y \le N\)
For \(2^{nd}\) type of query
\(1 \le X \le N\)
\(1 \le Y \le 5 * 10^5\)