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 Sol{
	static class pair {
		private int val;
		private int id;
		public pair(int val, int id) {
			this.val = val;
			this.id = id;
		}
	}
	final public static int MOD = (int)1e9+7;
	final public static int mxA = 20;
	public static int arr[];
	public static int ans[];
	public static int basis[] = new int[mxA];
	public static long two[];
	public static List<pair> query[];
	public static int n, q, size;
	public static void main(String[] args) throws IOException{
		FastIO sc = new FastIO(System.in);
		PrintWriter out = new PrintWriter(System.out);
		n = sc.nextInt();
		q = sc.nextInt();
		query = new ArrayList[n];
		ans = new int[q];
		two = new long[n+1];
		arr = new int[n];
		two[0] = 1;
		for(int i=1; i<=n; ++i) {
			two[i] = (two[i-1]*2)%MOD;
		}
		for(int i=0; i<n; ++i) {
			arr[i] = sc.nextInt();
			query[i] = new ArrayList<>();
		}
		for(int i=0; i<q; ++i) {
			int l = sc.nextInt()-1;
			int x = sc.nextInt();
			query[l].add(new pair(x, i));
		}
		int idx = 0;
		for(int i= 0; i<n; ++i) {
			insert(arr[i]);
			for(pair p:query[i]) {
				int x = p.val;
				if(find(x)) {
					ans[p.id] = (int)two[i-size+1];
				}else {
					ans[p.id] = 0;
				}
			}
		}
		for(int i=0; i<q; ++i) {
			out.println(ans[i]);
		}
		out.close();
	}
	public static void insert(int mask) {
		for(int i=0; i<mxA; ++i) {
			if((mask&(1<<i))==0) continue;
			if(basis[i] == 0) {
				basis[i] = mask;
				++size;
				//System.out.println(mask + " " + i + " ");
				return;
			}
			mask^=basis[i];
		}
	}
	public static boolean find(int mask) {
		for(int i=0; i<mxA; ++i) {
			if((mask&(1<<i))==0) continue;
			
			if(basis[i] == 0 )return false;
			
			mask^=basis[i];
		}
		return true;
	}
    public static void ColumnSort(int arr[][], int col) { 
        Arrays.sort(arr, new Comparator<int[]>() { 
            @Override 
          public int compare(int[] entry1,  
                             int[] entry2) { 
            	Integer a = entry1[col];
            	Integer b = entry2[col];
            	return a.compareTo(b);
          } 
        }); 
    } 
	static class FastIO {
		 
		// Is your Fast I/O being bad?
 
		InputStream dis;
		byte[] buffer = new byte[1 << 17];
		int pointer = 0;
 
		public FastIO(String fileName) throws IOException {
			dis = new FileInputStream(fileName);
		}
 
		public FastIO(InputStream is) throws IOException {
			dis = is;
		}
 
		int nextInt() throws IOException {
			int ret = 0;
 
			byte b;
			do {
				b = nextByte();
			} while (b <= ' ');
			boolean negative = false;
			if (b == '-') {
				negative = true;
				b = nextByte();
			}
			while (b >= '0' && b <= '9') {
				ret = 10 * ret + b - '0';
				b = nextByte();
			}
 
			return (negative) ? -ret : ret;
		}
 
		long nextLong() throws IOException {
			long ret = 0;
 
			byte b;
			do {
				b = nextByte();
			} while (b <= ' ');
			boolean negative = false;
			if (b == '-') {
				negative = true;
				b = nextByte();
			}
			while (b >= '0' && b <= '9') {
				ret = 10 * ret + b - '0';
				b = nextByte();
			}
 
			return (negative) ? -ret : ret;
		}
 
		byte nextByte() throws IOException {
			if (pointer == buffer.length) {
				dis.read(buffer, 0, buffer.length);
				pointer = 0;
			}
			return buffer[pointer++];
		}
 
		String next() throws IOException {
			StringBuffer ret = new StringBuffer();
 
			byte b;
			do {
				b = nextByte();
			} while (b <= ' ');
			while (b > ' ') {
				ret.appendCodePoint(b);
				b = nextByte();
			}
 
			return ret.toString();
		}
 
	}
}