# 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

## Source

2014 Multi-University Training Contest 1