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≤b_i≤a_i，0≤i≤n-1，b_i is a integer.
2)b₀ xor b₁ xor ... xor b_n-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.

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≤a_i≤1000).
Then next m lines. Each line is one of the follow two:
1)C x y: set the value of a_x 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.

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