# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## Hardest Update and Easiest Query

You have an array A with n elements which is indexed from 1 to n. Now you have to deal with two types of operations.

Update i’th index of array A with value v. This is represented by the command ‘1 i v’. (1 <= i <= n) && (1 <= v <= 1000000000).

Find the total sum of all possible pair (A[i] * A[j]) between L to R where L <= i < j <= R. This is represented by the command ‘2 L R’. (1 <= L <= R <= n).

### Input

Input starts with an integer n (<=100000), denoting the number of elements of the array A. Next line contains n integers, the elements of the array A. Elements of array are in 1 to 1000000000. Third line contains an integer q, denoting the number of query (1 <= q <= 100000). Then next q lines contain any type of operations.

### Output

Print the answer for each of the second type of operation with modulo 1000000007.

### Samples

Input | Output |
---|---|

5 1 2 3 4 5 5 2 1 3 1 1 3 2 1 3 1 3 1 2 1 3 | 11 21 11 |