Function F is defined as,

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

where GCD is the Greatest Common Divisor.

Given an array A of size N, there are 2 types of queries:
1. 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))\)
2. U X Y: Update the element of array \(A[X] = Y\)

Input:
First line of input contains integer N, size of the array.
Next line contains N space separated integers the elements of A.
Next line contains integer Q, number of queries.
Next Q lines contains 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 \cdot 10^5\)

For Update ,
\(1 \le X \le N\)
\(1 \le Y \le 5 \cdot 10^5\)

For Compute,
\(1 \le X \le Y \le N\)