问题 D: GG and YY's Binary Number

GG and YY are honing their skills with binary numbers. They have a set $V$ comprising $n$ binary numbers: �=�1,�2,…,��V=v1,v2,…,vn. Additionally, they have $m$ queries determined by intervals [�1,�1],[�2,�2],…,[��,��][l1,r1],[l2,r2],…,[lm,rm]. For each query interval [��,��][li,ri], 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 [��,��][li,ri]. The results should be provided modulo 109+7109+7.

Specifically, for each [��,��][li,ri], compute:

（∑j∈[li,ri]∑u1,u2,…,uk⊆V∑[u1⊕u2⊕…⊕uk=j]mod(109+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, [�1⊕�2⊕…⊕��=�][u1⊕u2⊕…⊕uk=j] is $1$ if the xor sum of �1,�2,…,��u1,u2,…,uk equals $j$, and $0$ otherwise.

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 �1,…,��v1,…,vn (0≤��<22500≤vi<2250), indicating the binary integers in $V$.

The following $m$ lines present the $m$ queries. The $i$-th line continas two binary integers ��,��li,ri (0≤��≤��<22500≤li≤ri<2250), 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$.

1
4 2
100 0 1 101
1 10
10 100

4
4