问题 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: V = {v1, v2, . . . , vn}. Additionally, they have m queries determined by intervals [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 + 7. Specifically, for each [li , ri ], compute:   X j∈[li,ri] X {u1,u2,...,uk}⊆V [u1 ⊕ u2 ⊕ . . . ⊕ uk = j]   mod (109 + 7) where ⊕ represents the xor operation and square brackets [·] 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, [u1 ⊕ u2 ⊕ . . . ⊕ uk = j] is 1 if the xor sum of u1, u2, . . . , uk equals j, and 0 otherwise.

The first line contains one integer t (1 ≤ t ≤ 100), indicating the number of test cases. The first line of each case contains two integers n and m (1 ≤ n, m ≤ 250), indicating the size of the sets V and W. The following line contains n binary integers v1, . . . , vn (0 ≤ vi < 2 250), 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 ≤ li ≤ ri < 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.

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

1
4 2
100 0 1 101
1 10
10 100

4
4