P17152 [ICPC 2017 Xi'an R] Sum of xor sum

Song Zha Zha has an $1$-indexed array $A$. Li Zha Zha has $Q$ queries. Each query has two integers $L$, $R$, asking Ran Zha Zha to do the following thing: First, find all subintervals of $[L, R]$. Then calculate their XOR sum. For example: $A = \{1, 2, 3\}$, $L = 1$, $R = 3$. All subintervals of $[1, 3]$ are $[1, 1], [2, 2], [3, 3], [1, 2], [2, 3], [1, 3]$. Their XOR sum is $1 + 2 + 3 + (1 \oplus 2)+ (2 \oplus 3) + (1 \oplus 2 \oplus 3)$. XOR means exclusive or (`^` in C++ or Java).

The input contains multiple test cases. First line contains an integer $T$ $(1 \le T \le 10)$, which is the number of test cases. In each test case: The first line contains two integers $N$, $Q$. $(1 \le N, Q \le 100000)$. $N$ is the length of the array $A$. Then one line contains $N$ integers indicating $A[i]$. $(1 \le i \le N, 0 \le A[i] \le 1000000)$. Then $Q$ lines follow. Each line has two integers $L, R$, meaning that there’s a query $[L, R]$. $(1 \le L \le R \le N)$.

For each query, print the answer mod $1000000007$.