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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
import java.util.StringTokenizer;

public class cf {
	public static void main(String[] args) throws IOException {
		FastScanner in = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = in.nextInt();
		int q = in.nextInt();
		int[] arr = new int[n];
		for(int i=0;i<n;i++)
			arr[i] = in.nextInt();
		ArrayList<Query> list = new ArrayList<>();
		for(int i=0;i<q;i++) {
			list.add(new Query(i, in.nextInt()-1, in.nextInt()));
		}
		Collections.sort(list, Comparator.comparing(x -> x.l));
		ArrayDeque<Query> dq = new ArrayDeque();
		dq.addAll(list);
		ArrayList<Integer> gaussian = new ArrayList();
		long ret = 1;
		long[] ans = new long[q];
		for(int i=0;i<n;i++) {
			int cur = arr[i];
			for(int v : gaussian) {
				if((cur ^ v) < cur)
					cur ^= v;
			}
			if(cur != 0) {
				gaussian.add(cur);
				Collections.sort(gaussian, Collections.reverseOrder());
			} else {
				ret *= 2;
				ret %= (long)1e9+7;
			}
			while(!dq.isEmpty() && dq.peekFirst().l == i) {
				Query a = dq.pollFirst();
				cur = a.x;
				for(int v : gaussian) {
					if((cur ^ v) < cur)
						cur ^= v;
				}
				if(cur == 0) {
					ans[a.i] = ret;
				}
			}
		}
		for(int i=0;i<q;i++) {
			out.println(ans[i]);
		}
		out.close();
	}
	static class Query {
		int i,l,x;
		public Query(int ii, int ll, int xx) {
			i = ii;
			l = ll;
			x = xx;
		}
	}
	static class FastScanner {
	    BufferedReader br;
	    StringTokenizer st;
		
	    public FastScanner(InputStream i) {
	        br = new BufferedReader(new InputStreamReader(i));
	        st = new StringTokenizer("");
	    }
				
	    public String next() throws IOException {
	        if(st.hasMoreTokens())
	            return st.nextToken();
	        else
	            st = new StringTokenizer(br.readLine());
	        return next();
	    }

	    public int nextInt() throws IOException {
	        return Integer.parseInt(next());
	    }
	    public long nextLong() throws IOException {
	        return Long.parseLong(next());
	    }
	    public double nextDouble() throws IOException {
	        return Double.parseDouble(next());
	    }
	}
}
