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.

1. 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).

2. 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.

Sample

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