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.

Input

The first line contains integers n and q (1 ≤ n, q ≤ 105), the number of elements in the array and the number of queries.

The next line contains n integers a1, a2, ..., an (0 ≤ ai < 220), the elements of the array.

The next q lines, each contains integers l and x (1 ≤ l ≤ n, 0 ≤ x < 220), representing the queries.

Output

For each query, output its answer modulo 109 + 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.
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

public class MahmoudAndEhabAndYetAnotherXorTask {
	static int mod = 1000000007;

	static class Reader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public Reader() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public Reader(String file_name) throws IOException {
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public String readLine() throws IOException {
			byte[] buf = new byte[10005]; // line length
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n')
					break;
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, cnt);
		}

		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg)
				return -ret;
			return ret;
		}

		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}

		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();

			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}

			if (neg)
				return -ret;
			return ret;
		}

		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer();
			return buffer[bufferPointer++];
		}

		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}
	}

	static int LOG_A = 20;

	static int basis[] = new int[LOG_A]; // basis[i] keeps the mask of the vector whose f value is i

	static int sz; // Current size of the basis

	static void insertVector(int mask) {
		for (int i = 0; i < LOG_A; i++) {
			if ((mask & (1 << i)) == 0)
				continue; // continue if i != f(mask)

			if (basis[i] == 0) { // If there is no basis vector with the i'th bit set, then insert this vector
									// into the basis
				basis[i] = mask;
				++sz;

				return;
			}

			mask ^= basis[i]; // Otherwise subtract the basis vector from this vector
		}
	}

	static boolean isPossible(int mask) {
		int i;
		for (i = 0; i < LOG_A; i++) {
			if ((mask & (1 << i)) == 0)
				continue;
			if (basis[i] == 0)
				return false;
			mask ^= basis[i];
		}
		return true;

	}

	static List<Integer> q_at[];

	public static void main(String[] args) throws IOException {
		Reader in = new Reader();
		int i, q, n, t;
		n = in.nextInt();
		q = in.nextInt();
//		Arrays.fill(basis, -1);
		q_at = new ArrayList[n + 1];
		for (i = 0; i <= n; i++) {
			q_at[i] = new ArrayList<>();
		}
		int a[] = new int[n + 1];
		for (i = 1; i <= n; i++) {
			a[i] = in.nextInt();
		}

		int queries[][] = new int[q + 1][2];
		i = 1;
		t = q;
		while (t-- > 0) {
			queries[i][0] = in.nextInt();
			queries[i][1] = in.nextInt();
			q_at[queries[i][0]].add(i);
			i++;
		}

		long power[] = new long[n + 1];
		power[0] = 1;
		for (i = 1; i <= n; i++) {
			power[i] = (power[i - 1] * 2) % mod;
		}
		long ans[] = new long[q + 1];
		for (i = 1; i <= n; i++) {
			insertVector(a[i]);
//			System.out.println(a[i] + " added, sz " + sz);
//			System.out.println(q_at[i]);
			for (int x : q_at[i]) {
//				System.out.println("x " + x + " q " + queries[x][1]);
				if (isPossible(queries[x][1])) {
//					System.out.println("in" + " q " + queries[x][1] + " s " + sz);
					ans[x] = power[i - sz];
				}
			}
		}

		StringBuilder out = new StringBuilder();
		for (i = 1; i <= q; i++) {
			out.append(ans[i] + "\n");
		}
		System.out.println(out);
	}
}
