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.*;
import java.util.*;

public class Codeforces959F {
	public static void main (String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		String[] sp = br.readLine().split(" ");
		int n = Integer.parseInt(sp[0]);
		int q = Integer.parseInt(sp[1]);
		
		int[] a = new int[n];
		sp = br.readLine().split(" ");
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(sp[i]);
		}
		
		//create row echelon, 1 at a time
		int[][] rowEchelon = new int[20][];
		for (int i = 0; i < 20; i++) {
			rowEchelon[i] = new int[i+1];
		}
				
		int[] qList = new int[20];
		for (int i = 0; i < 20; i++) {
			qList[i] = 1000000000;
		}
		int counter = 0;
		for (int iter = 0; (iter < n) && (counter < 20); iter++) {
			if (counter == 0) {
				if (a[iter] != 0) {
					rowEchelon[0][0] = a[iter];
					qList[counter] = iter;
					counter++;
				}
			}
			else {
				int[] pair = reduced(a[iter], rowEchelon[counter-1]);
				if (pair[0] != 0) {
					int k = pair[1];
					for (int i = 0; i < k; i++) {
						rowEchelon[counter][i] = rowEchelon[counter-1][i];
					}
					rowEchelon[counter][k] = pair[0];
					for (int i = k+1; i <= counter; i++) {
						rowEchelon[counter][i] = rowEchelon[counter-1][i-1];
					}
					qList[counter] = iter;
					counter++;
				}
			}
		}
		counter--;
		
		for (int i = 0; i < q; i++) {
			sp = br.readLine().split(" ");
			int l = Integer.parseInt(sp[0]);
			int x = Integer.parseInt(sp[1]);
			
			int rows = -1;
			while ((rows < counter) && (qList[rows+1] < l)) {
				rows++;
			}
			
			if (rows == -1) {
				if (x == 0) {
					pw.println(power(2, l, 1000000007));
				}
				else {
					pw.println(0);
				}
			}
			else {
				int[] pair = reduced(x, rowEchelon[rows]);
				if (pair[0] != 0) {
					pw.println(0);
				}
				else {
					pw.println(power(2, (l-rows-1), 1000000007));
				}
			}
		}
		pw.close();
	}
	
	public static int[] reduced(int original, int[] listF2) {
		int l = listF2.length;
		int counter = 0;
		boolean bool = true;
		while (bool && (counter < l)) {
			if (original > listF2[counter]) {
				if ((original^listF2[counter]) < listF2[counter]) {
					original = original^listF2[counter];
					counter++;
				}
				else {
					bool = false;
				}
			}
			else {
				if ((original^listF2[counter]) < original) {
					original = original^listF2[counter];
				}
				counter++;
			}
		}
		int[] ans = {original, counter};
		return ans;
	}
	
	public static int power(int base, int exp, int mod) {
		long a = base%mod;
		if (exp == 0) {
			return 1;
		}
		else {
			a = (a*a)%mod;
			int b = (int) a;
			int almostanswer = power(b, exp/2, mod);
			if (exp%2 == 0) {
				return almostanswer;
			}
			else {
				long val = (long) almostanswer * (long) base;
				long val2 = val%mod;
				return (int) val2;
			}
		}
	}
}
