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

public class F959{
	public static class FastReader {
		BufferedReader br;
		StringTokenizer root;
		
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (root == null || !root.hasMoreTokens()) {
				try {
					root = new StringTokenizer(br.readLine());
				} catch (Exception r) {
					r.printStackTrace();
				}
			}
			return root.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception r) {
				r.printStackTrace();
			}
			return str;
		}
	}
	
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	static long mod = (long) (1e9+7);
	static long cf = 998244353;
    static  int MAX = 1005,n,m;
    public static List<Pair>[] q;
    public static long[][] dp;
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] a = new int[n+1];
		long[] qans = new long[m+1];
		q = new ArrayList[n+1];
		for(int i=0;i<q.length;++i) q[i] = new ArrayList<>();
		for(int i=1;i<=n;++i) a[i] = sc.nextInt();
		for(int i=1;i<=m;++i) 
			q[sc.nextInt()].add(new Pair(sc.nextInt(),i));
		Set<Long> set = new HashSet<>();
		set.add(0L);
		long ans = 1;
		for(int i=1;i<=n;++i) {
			if(set.contains((long)a[i])) ans = (2*ans)%mod;
			else {
				Set<Long> temp = new HashSet<>();
				for(long x : set) temp.add(x^a[i]);
				set.addAll(temp);
 			}
			// ans is same of all xor x till i
			for(Pair p : q[i]) {
				if(set.contains((long)p.x)) qans[p.y] = ans;
			}
 		}
		for(int i=1;i<=m;++i) out.println(qans[i]);
	    out.close();
	}
	static class Pair{
		int x;
		int y;
		Pair(int x,int y){
			this.x = x;
			this.y = y;
		}
	}
}