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.
Input
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$
Output
Print a response for each query in a separate line.
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.
