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$