wyh2000 and sequence

Young theoretical computer scientist wyh2000 is concentrating on studying data structures.

In order to show his wisdom, he gives his students a hard problem.

Wyh2000 gives a sequence $A_1,A_2,\ldots,A_n$.He would ask his students $q$ times,each time he gives $l,r$.Suppose $[l, r]$ have $k$ different numbers $c_1,c_2,\ldots,c_k$,and $c_i$ appears $b_i$ times in the interval $[l, r]$,the students should tell him the value of $\sum_{i=1}^{k}c_i^{b_i}$ modulo $1000000007$,you should use online algorithm.

In the first line, there is an integer $T$ indicates the number of test cases.

For each case, the first line contains two integers $n,q$,the second line contains $n$ integers $A_1,A_2,\ldots,A_n$.

In the next $q$ lines,each line contains 2 intergers $a,b$.Query parameters $l,r$ are obtained from the numbers $a,b$.$l=\min((a \oplus la)\%n+1,(b \oplus la)\%n+1),r=\max((a \oplus la)\%n+1,(b \oplus la)\%n+1)$

The $\oplus$ means xor,and $la$ equals the response for the previous query.$la=0$ when each case begin.

$T\leq5,1\leq A_i,a,b\leq10^9$

In the $i$th case,$1\leq n,q\leq i\times10000$

Print a response for each query in a separate line.

2
5 3
2 1 2 3 1
10 14
9 8
8 7
5 2
2 3 3 2 2
7 4
3 6

8
3
6
7
13

In the first case，the inquiry intervals are $[1,5],[1,2],[2,5]$.
In the second case，the inquiry intervals are $[3,5],[2,5]$.
Don't add extra spaces after any line of your hack data.

BestCoder Round #48 ($)