题目描述

Song Zha Zha 有一个下标从 $1$ 开始的数组 $A$。Li Zha Zha 有 $Q$ 个询问。每个询问给出两个整数 $L$、$R$，要求 Ran Zha Zha 做以下事情：首先找出 $[L, R]$ 的所有子区间，然后计算这些子区间的异或值之和。例如：

$A = \{1, 2, 3\}$，$L = 1$，$R = 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)$。

XOR 表示按位异或（C++ 或 Java 中的 ^ 运算符）。

输入格式

输入包含多组测试数据。

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

对于每组测试数据：

第一行包含两个整数 $N$ 和 $Q$ ($1 \le N, Q \le 100000$)，其中 $N$ 是数组 $A$ 的长度。

接下来一行包含 $N$ 个整数，表示 $A[i]$ ($1 \le i \le N$，$0 \le A[i] \le 1000000$)。

随后 $Q$ 行，每行包含两个整数 $L$ 和 $R$，表示一个询问 $[L, R]$ ($1 \le L \le R \le N$)。

输出格式

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

1
3 1
1 2 3
1 3

10

提示

翻译由 DeepSeek V4 Pro 完成