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.util.*;
import java.io.*;
public class F{
    static PrintWriter out;
    static InputReader in;
    public static void main(String args[]){
        out = new PrintWriter(System.out);
        in = new InputReader();
        new F();
        out.flush(); out.close();
    }   
    F(){
        solve();
    }
    class pair{
        int F, S, T;
        pair(int a, int b, int c){
            F = a; S = b; T = c;
        }
    }
    final int mod = (int)(1e9) + 7;
    final int maxb = 20, max = 100010;

    int n, q;
    int a[], cnt = 0;
    long ans[];
    long p2[] = new long[max];
    ArrayList<pair> al = new ArrayList<>();
    BitSet bs[] = new BitSet[maxb];

    void add(int x){
        int currentBit = 0;
        BitSet a = new BitSet(maxb);
        while(x != 0){
            if((x & 1) == 1) a.set(currentBit);
            currentBit++; x >>= 1;
        }
        for(int i = maxb - 1; i >= 0; i--){
            if(a.get(i))a.xor(bs[i]);
        }
        for(int i = maxb - 1; i >= 0; i--){
            if(a.get(i)){
                bs[i] = a; return;
            }
        }
        cnt++;
    }

    long count(int x){
        int currentBit = 0;
        BitSet a = new BitSet(maxb);
        while(x != 0){
            if((x & 1) == 1) a.set(currentBit);
            currentBit++; x >>= 1;
        }
        for(int i = maxb - 1; i >= 0; i--){
            if(a.get(i))a.xor(bs[i]);
        }
        if(a.cardinality() != 0) return 0;
        return p2[cnt];
    }

    void solve(){
        p2[0] = 1;
        for(int i = 1; i < max; i++)p2[i] = p2[i - 1] * 2 % mod;

        n = in.nextInt(); q = in.nextInt();
        a = new int[n]; ans = new long[q];
        for(int i = 0; i < n; i++)a[i] = in.nextInt();
        for(int i = 0; i < q; i++){
            al.add(new pair(in.nextInt(), in.nextInt(), i));
        }
        Collections.sort(al, (A, B) -> A.F - B.F);
        int start = 0;
        for(int i = 0; i < maxb; i++){
            bs[i] = new BitSet(maxb);
        }
        for(int i = 0; i < q; i++){
            pair p = al.get(i);
            for(int j = start; j < p.F; j++){
                add(a[j]);
            }
            ans[p.T] = count(p.S);
            start = p.F;
        }
        for(int i = 0; i < q; i++){
            out.println(ans[i]);
        }
    }
    public static class InputReader{
        BufferedReader br;
        StringTokenizer st;
        InputReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        public int nextInt(){
            return Integer.parseInt(next());
        }
        public long nextLong(){
            return Long.parseLong(next());
        }
        public double nextDouble(){
            return Double.parseDouble(next());
        }
        public String next(){
            while(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch(IOException e){}
            }
            return st.nextToken();
        }
    }
}
        