Students of Computer Science department at NIT Durgapur were becoming extremely bored and frustrated due to too many classes ( weird but we had many classes ). As semesters were approaching , students were preparing hard to get good grades. Everyone was nervous about the Algorithms exam which is going to be held 2 days later. To add to their discomfort, one question came in the exam which took many one by surprise. The question was simple but everyone was told to optimize code as much as possible.

Now its your turn, and the question states that there is intially an array of N non-negative numbers (1-based indexing) and based on that array we have to run Q queries. Now we can do three things in each query. We have to sometimes calculate sum of product of all subsets of a number within a range, sometimes to calculate sum of Bitwise AND of all subsets of a number, sometimes to update an element of an array. All the calculations are to be performed modulus (109+7). If we have to do sum of products then the query is given 'M', if Bitwise AND then 'A' else if update then 'U'. For more details , see Explanation section .

Note : Bitwise AND operator is defined as & in C ,C++ and in most of the languages. For other programming languages see your language documentation.

Input Format
First line contains N, which denotes the number of elements in an array. Next line contains N integers denoting the number of integers in the array. Then Q denoting the number of queries and after that each line consists of 3 integers. If it is 'M' then we have to do product, if 'A' then Bitwise AND and if 'U' then update. If it is 'M' or 'A' then it is followed by i and j which is the range of that array. If 'U' then we have the positon and the value to be updated at that position.

Output Format
Corresponding to each query we have an output only to query of 'M' and 'A'. For update you dont have to print anything.

Constraints
1 ≤ N ≤ 105
1 ≤ A[i] ≤ 105
1 ≤ Q ≤ 105
1 ≤ i ≤ j ≤ 105
The element to be updated is of maximum value of 105.

Sample Input
3
1 2 3
5
M 1 3
A 1 3
U 2 5
M 1 3
A 1 3

Sample Output
23
9
47
13

Explanation
For 1st query, we do 1 + 2 + 3 + 1*2 + 1*3 + 2*3 + 1*2*3 =23
For 2nd query, it is 1 + 2 + 3 + 1&2 + 1&3 + 2&3 + 1&2&3 = 9
For 3rd query, it is update so array becomes 1 5 3
For 4th query, it is 1 + 5 + 3 + 1*5 + 1*3 + 3*5 + 1*3*5 = 47
For 5th query, it is 1 + 5 + 3 + 1&5 + 1&3 + 3&5 + 1&3&5 = 13