Song Zha Zha 有一个长度为 $N$ 的序列 $A$。Li Zha Zha 有 $Q$ 个询问。每个询问提供两个整数 $L$ 和 $R$，表示一个闭区间 $[L, R]$。Ran Zha Zha 列出了 $[L, R]$ 的所有子区间。对于每个子区间 $[s, t]$，他计算 $A$ 中从第 $s$ 个元素到第 $t$ 个元素的异或和。然后他将所有这些异或和相加，所得的总和即为他所需要的结果。这里“异或”指的是“按位异或”，对应 C++ 和 Java 中的 ^ 运算。

以序列 $A=[1, 2, 3]$ 为例，$L=1$，$R=3$ 表示区间 $[1, 3]$。我们列出 $[1, 3]$ 的所有子区间： $[1, 1], [2, 2], [3, 3], [1, 2], [2, 3]$ 和 $[1, 3]$。

它们的异或和分别为 $1, 2, 3, 1 \oplus 2, 2 \oplus 3$ 以及 $1 \oplus 2 \oplus 3$。上述所有异或和的总和为 $1+2+3+(1 \oplus 2)+(2 \oplus 3)+(1 \oplus 2 \oplus 3)$。

在本题中，你需要针对多个询问，计算所有子区间的异或和之总和。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试数据的组数。

对于每组测试数据，第一行包含两个整数 $N$ 和 $Q$ ($1 \le N, Q \le 100000$)，其中 $N$ 是数组 $A$ 的长度，$Q$ 是询问次数。第二行包含 $N$ 个整数 $A[1]$ 到 $A[N]$，表示该序列 ($0 \le A[i] \le 1000000$，对于每个 $i \in [1, N]$)。接下来 $Q$ 行，每行描述一个询问，包含两个整数 $L$ 和 $R$，表示区间 $[L, R]$，其中 $1 \le L \le R \le N$。所有测试数据中 $N$ 和 $Q$ 的总和小于 $400000$。

输出格式

对于每个询问，输出答案对 $1000000007$ 取模的结果。

样例

输入 1

1
3 1
1 2 3
1 3

输出 1

10