Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Mahmoud and Ehab and yet another xor task

time limit per test

1 secondmemory limit per test

512 megabytesinput

standard inputoutput

standard outputEhab has an array *a* of *n* integers. He likes the bitwise-xor operation 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.

Input

The first line contains integers *n* and *q* (1 ≤ *n*, *q* ≤ 10^{5}), the number of elements in the array and the number of queries.

The next line contains *n* integers *a*_{1}, *a*_{2}, ..., *a*_{n} (0 ≤ *a*_{i} < 2^{20}), the elements of the array.

The next *q* lines, each contains integers *l* and *x* (1 ≤ *l* ≤ *n*, 0 ≤ *x* < 2^{20}), representing the queries.

Output

For each query, output its answer modulo 10^{9} + 7 in a newline.

Examples

Input

5 5

0 1 2 3 4

4 3

2 0

3 7

5 7

5 8

Output

4

2

0

4

0

Input

3 2

1 1 1

3 1

2 0

Output

4

2

Note

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/22/2018 01:20:26 (f1).

Desktop version, switch to mobile version.

User lists

Name |
---|