Ehab has an array *a* of *n* integers. He likes the [bitwise-xor operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) and he likes to bother Mahmoud so he came up with a problem. He gave Mahmoud *q* queries. In each of them, he gave Mahmoud 2 integers *l* and *x*, and asked him to find the number of subsequences of the first *l* elements of the array such that their bitwise-xor sum is *x*. Can you help Mahmoud answer the queries?

A subsequence can contain elements that are not neighboring.
The first line contains integers *n* and *q* (1 ≤ *n*, *q* ≤ 10<sup class="upper-index">5</sup>), the number of elements in the array and the number of queries.

The next line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (0 ≤ *a*<sub class="lower-index">*i*</sub> &lt; 2<sup class="upper-index">20</sup>), the elements of the array.

The next *q* lines, each contains integers *l* and *x* (1 ≤ *l* ≤ *n*, 0 ≤ *x* &lt; 2<sup class="upper-index">20</sup>), representing the queries.
The bitwise-xor sum of the empty set is 0 and the bitwise-xor sum of a set containing one element is that element itself.
5 5
0 1 2 3 4
4 3
2 0
3 7
5 7
5 8
4
2
0
4
0
3 2
1 1 1
3 1
2 0
4
2
20 20
353123 353123 677328 353123 0 997043 677328 420884 968991 566539 420884 801220 1030642 937882 762558 599450 196420 299659 101896 600581
14 764540
10 140147
20 631492
15 403662
14 730429
11 566539
2 353123
9 353123
18 463456
15 714519
16 418098
8 623050
10 369379
9 801220
11 705280
3 156540
4 507911
10 338945
11 496568
1 360148
256
0
1024
0
256
128
2
32
256
0
0
0
0
32
0
0
0
0
128
0
20 20
306892 1035619 634501 191090 883124 315497 52694 533023 671659 798312 656827 376229 777308 233774 1044523 889658 1001600 326577 1019534 723866
19 454109
12 293130
11 1024526
9 97284
8 418790
1 306892
16 795066
5 1020870
20 526791
18 338417
17 990717
11 101307
12 792824
18 108354
1 158141
20 471906
14 180513
5 100587
1 752042
15 704444
512
4
2
1
1
1
0
1
1024
0
128
0
4
256
0
1024
0
0
0
0
5 6
4 4 0 14 14
2 2
4 10
5 4
3 0
5 4
2 4
0
4
8
4
8
2
11 3
8 290 0 298 8 290 290 290 298 8 0
2 290
9 311
10 487
1
0
0
20 4
3543 10760 559 23602 14947 30833 5084 17919 10471 10689 21846 11925 23128 11184 24426 19945 19340 4464 9112 21680
2 4015
2 18599
7 31496
10 11700
0
0
0
0
9 7
0 0 2 2 3 2 3 0 1
3 3
9 1
7 0
4 1
8 3
4 1
9 0
0
128
32
0
64
0
128
13 18
2 0 0 0 0 0 1 1 1 0 3 3 1
5 2
11 2
1 4
12 7
11 4
2 2
6 1
13 0
2 5
9 1
5 5
2 2
7 4
11 4
8 5
10 4
3 3
12 6
16
512
0
0
0
2
0
2048
0
128
0
2
0
0
0
0
0
0
2 2
3 1
2 3
1 0
1
1
3 7
2 3 3
3 1
2 0
2 1
1 0
3 2
2 3
1 0
2
1
1
1
2
1
1
3 10
3 6 5
2 4
3 1
2 4
3 0
2 5
2 5
2 6
2 0
1 3
2 7
0
0
0
2
1
1
1
1
1
0
3 18
0 1 2
1 0
3 3
1 0
2 1
2 0
2 1
3 5
3 3
2 2
3 1
2 4
2 1
2 0
2 2
1 7
1 0
3 2
3 4
2
2
2
2
2
2
0
2
0
2
0
2
2
0
0
2
2
0
4 3
3 10 9 0
1 3
4 9
2 9
1
4
1
9 10
10 16 16 10 0 0 26 0 16
1 14
1 10
2 16
1 21
8 16
8 26
6 16
2 26
3 10
7 22
0
1
1
0
64
64
16
1
2
0
5 8
0 0 0 14 6
2 12
4 3
4 5
5 0
1 13
5 7
4 12
2 0
0
0
0
8
0
0
0
4
8 2
0 0 0 11 2 36 61 2
8 53
7 10
0
0
2 4
1 2
1 3
2 3
1 2
1 3
0
1
0
0
3 5
3 1 7
3 2
3 1
2 3
3 0
2 2
1
1
1
1
1
6 7
4 4 4 3 1 3
4 4
6 4
1 3
2 4
3 0
6 4
1 3
4
8
0
2
4
8
0
3 8
3 2 4
3 4
2 7
1 2
3 1
3 5
3 1
2 7
2 4
1
0
0
1
1
1
0
0
3 15
4 3 1
3 2
3 2
3 7
1 6
3 7
2 0
1 0
1 3
1 4
3 3
3 1
1 4
1 4
2 6
1 0
1
1
1
0
1
1
1
0
1
1
1
1
1
0
1
4 19
2 5 6 4
1 3
4 4
1 0
1 7
4 3
4 5
3 2
4 1
1 0
2 2
3 2
1 0
4 1
4 1
2 6
1 2
2 6
2 4
1 7
0
2
1
0
2
2
1
2
1
1
1
1
2
2
0
1
0
0
0
5 9
5 4 7 4 7
2 4
3 5
2 3
5 7
3 2
3 5
2 5
1 5
5 7
1
1
0
4
1
1
1
1
4
9 5
0 0 30 30 0 0 52 43 53
4 45
4 23
2 63
2 0
1 0
0
0
0
4
2
10 10
0 31 62 32 0 62 32 30 30 33
2 34
7 49
10 31
5 46
8 12
4 24
6 15
7 52
9 30
2 0
0
0
128
0
0
0
0
0
64
2
6 6
4 3 11 2 2 4
3 1
5 13
3 8
3 4
3 8
1 8
0
2
1
1
1
0
8 5
0 0 127 127 48 0 66 253
6 79
1 111
4 0
7 213
1 126
16
0
8
0
0
17 5
234 55 212 253 148 148 212 163 96 55 0 163 157 131 94 119 189
2 55
11 172
8 41
7 135
14 180
1
0
8
0
512
10 9
286 621 876 0 31 883 31 257 163 670
8 257
6 196
3 883
2 286
1 286
8 252
2 572
6 565
6 626
32
0
1
1
1
0
0
0
8
7 10
3 2 1 0 2 3 3
6 1
5 1
4 3
3 0
6 2
3 3
1 3
4 0
7 1
7 3
16
8
4
2
16
2
1
4
32
32
13 16
201 2016 1726 1340 2030 1712 2030 0 1650 983 1299 838 1670
3 1995
3 1412
4 667
10 78
13 1377
12 1388
6 837
4 2016
6 1531
1 0
12 2012
10 905
12 1040
10 284
3 2016
12 1819
0
0
0
0
8
8
2
1
2
1
0
8
8
0
1
0
7 10
1 7 2 3 0 3 2
5 0
1 0
6 2
7 1
3 2
3 7
1 2
4 2
5 3
3 4
4
1
8
16
1
1
0
2
4
1
9 10
0 0 72 177 1 167 95 72 23
9 0
1 149
2 0
6 94
7 176
6 177
2 0
1 198
6 239
9 221
32
0
4
4
8
4
4
0
4
0
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

n, q = map(int, input().split())
mod = pow(10, 9) + 7
a = list(map(int, input().split()))
y = [[] for _ in range(n)]
for i in range(q):
    l, x = map(int, input().split())
    y[l - 1].append((x, i))
m = pow(2, 20)
dp = [0] * m
dp[0] = 1
now = 1
ans = [0] * q
for i in range(n):
    u = a[i]
    if not dp[u]:
        for j in range(m):
            dp[j] |= dp[j ^ u]
    else:
        now *= 2
        now %= mod
    for x, j in y[i]:
        ans[j] = now * dp[x]
sys.stdout.write("\n".join(map(str, ans)))