GG and YY's Binary Number

Problem Description

GG and YY are honing their skills with binary numbers. They have a set $V$ comprising $n$ binary numbers: $V = \{v_1, v_2, \ldots, v_n\}$. Additionally, they have $m$ queries determined by intervals $[l_1, r_1], [l_2, r_2], \ldots, [l_m, r_m]$. For each query interval $[l_i, r_i]$, they aim to compute the count of unique subsets $U$ taken from $V$ such that the xor sum of the elements of $U$ lies within $[l_i, r_i]$. The results should be provided modulo $10^9 + 7$. Specifically, for each $[l_i, r_i]$, compute:

$$\left( \sum_{j \in [l_i, r_i]} \sum_{\{u_1, u_2, \ldots, u_k\} \subseteq V} [u_1 \oplus u_2 \oplus \ldots \oplus u_k = j] \right) \bmod (10^9 + 7) $$

where $\oplus$ represents the xor operation and square brackets $[\cdot]$ denote the Iverson bracket. Please note that the xor sum of an empty set is $0$. In the Iverson bracket notation, if the condition inside the bracket is true, the value is $1$; otherwise, it is $0$. For instance, $[u_1 \oplus u_2 \oplus \ldots \oplus u_k = j]$ is $1$ if the xor sum of $u_1, u_2, \ldots, u_k$ equals $j$, and $0$ otherwise.

Input

The first line contains one integer $t$ ($1 \le t \le 100$), indicating the number of test cases. The first line of each case contains two integers $n$ and $m$ ($1\le n,m\le 250$), indicating the size of the sets $V$ and $W$. The following line contains $n$ binary integers $v_1,\ldots,v_n$ ($0\le v_i< 2^{250}$), indicating the binary integers in $V$. The following $m$ lines present the $m$ queries. The $i$-th line continas two binary integers $l_i,r_i$ ($0\le l_i\le r_i<2^{250}$), indicating the query interval. It is guaranteed that there will be no leading zeros in the binary numbers, with the exception of $0$. For instance, the binary number $110$ corresponds to the decimal number $6$.

Output

For each test case, output $m$ integers in $m$ lines, indicating the results of the queries.

Sample Input

1
4 2
100 0 1 101
1 10
10 100

Sample Output

4
4

Source

2023“钉耙编程”中国大学生算法设计超级联赛（8）