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 F implements Runnable{
	public static void main (String[] args) {new Thread(null, new F(), "_cf", 1 << 28).start();}

	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("Go!");

		/*
		 * Generate set of all possible xor subsequences (there are only 2^20 possible ones)
		 * When seeing if a[i] can make new any new xor values, it can only do that if it
		   isn't already in the set.
		 * Every number in the set is a result of being xored by an a[i] and some other
		   number in the set (except 0)
		 * If we take an a[i] already in the set and xor it with every value in the
		   set then we'll just get the initial a[j] that was used to get that xor 
		   value in the first place.
		   If a[i] was put in the sequence as a result of a[j] ^ some x (where x is every
		   element that was in the set at the time of a[j]'s insertion) then when I
		   xor a[i] with itself, I'll get a[j] which I know is already in the set.
		   Xor-ing with any other number will similarly also give me another number
		   already in the set.
		 * Initially there's always one way to get the initial set (initial set is 0 and
		   you can pick the empty set to get it).
		   If you get to an a[i] that is in the set already, then regardless of what x
		   value is queried (as long as it's also in the set) then there will be 2 times
		   as many ways to get x. If x is in the set already, then I can just build off of
		   those subsequences without adding a[i] and now that I know that a[i] is in the set
		   then a[i] ^ x is also forced to be in the set (editorial has a good explanation imo)
		   in which case I can also build off of the sequences that xor to (a[i] ^ x) and when I
		   xor with a[i] I just get x.
		   The above also applies to any a[i] in the set as long as both a[i] and x are in the set.
		   This depends on the fact that if x is in the set and a[i] is in the set, then a[i] ^ x has
		   to also be in the set.
		 * If a[i] or x is not already in the set, then it's possible that I will still be able to
		   build off of the subsequences that have the value that will get me x when I xor with a[i]
		   in which case there aren't 2 times as many ways but still the same number of ways (as long
		   as x is in the set).
		 */
		
		int n = fs.nextInt();
		int q = fs.nextInt();
		int[][] qs = new int[2][q];
		ArrayList<Integer>[] queries = new ArrayList[n];
		for(int i = 0; i < n; i++) queries[i] = new ArrayList<>();
		
		int[] a = fs.nextIntArray(n);
		for(int i = 0; i < q; i++) {
			qs[0][i] = fs.nextInt() - 1;
			qs[1][i] = fs.nextInt();
			queries[qs[0][i]].add(i);
		}
		
		ArrayList<Integer> set = new ArrayList<>();
		boolean[] inSet = new boolean[1 << 20];
		inSet[0] = true;
		set.add(0);
		long ans = 1, MOD = (long)1e9+7;
		long[] res = new long[q];
		
		for(int i = 0; i < n; i++) {
			if(inSet[a[i]]) {
				ans = (2L * ans) % MOD;
			}
			else {
				int sz = set.size();
				for(int j = 0; j < sz; j++) {
					set.add(set.get(j) ^ a[i]);
					inSet[set.get(j) ^ a[i]] = true;
				}
			}
			
			for(Integer qq : queries[i]) {
				if(inSet[qs[1][qq]]) res[qq] = ans;
				else res[qq] = 0;
			}
			
		}

		for(long i : res) out.println(i);

		out.close();
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;
		public FastScanner() {
			try	{
				br = new BufferedReader(new InputStreamReader(System.in));
				//                br = new BufferedReader(new FileReader("testdata.out"));
				st = new StringTokenizer("");
			} catch (Exception e){e.printStackTrace();}
		}
		public String next() {
			if (st.hasMoreTokens())	return st.nextToken();
			try {st = new StringTokenizer(br.readLine());}
			catch (Exception e) {e.printStackTrace();}
			return st.nextToken();
		}
		public int nextInt() {return Integer.parseInt(next());}
		public long nextLong() {return Long.parseLong(next());}
		public double nextDouble() {return Double.parseDouble(next());}

		public String nextLine() {
			String line = "";
			try {line = br.readLine();}
			catch (Exception e) {e.printStackTrace();}
			return line;
		}
		public Integer[] nextIntegerArray(int n) {
			Integer[] a = new Integer[n];
			for(int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for(int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
		public char[] nextCharArray() {return nextLine().toCharArray();}
	}

}