Xor

Time Limit: 10000/5000 MS (Java/Others)

Memory Limit: 130712/130712 K (Java/Others)

Description

Given n non-negative integers, We define a statistical function as follows:

It will be noted that the nature of F(k) is calculated with the number of choices, such that:
1)0≤bi≤ai,0≤i≤n-1,bi is a integer.
2)b0 xor b1 xor ... xor bn-1 = k,xor means exclusive-or operation.  
Now given A and m operations, there are two different operations:
1)C x y: set the value of ax to y;
2)Q x: calculate F(x) mod P, where P = 1000000007.

Input

The first line has a number T (T ≤ 10), indicating the number of test cases.
For each test case, the first line contains tow integers n, m, (1≤n, m≤20000), denote the n, m that appear in the above description. Then next line contains n non-negative integers denote
(0≤ai≤1000).
Then next m lines. Each line is one of the follow two:
1)C x y: set the value of ax to y;(0≤x≤n-1,0≤y≤1000)
2)Q x: calculate F(x) mod P, where P = 1000000007.
The number of the first operation is not more than 5000.

Output

For each Q operation, output the value of F(x) mod P.

Sample Input

1 2 5 3 2 Q 3 C 0 2 Q 3 Q 0 C 0 3

Sample Output

3 2 3

Hint

Source

2014 Multi-University Training Contest 1

提交代码