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.StringTokenizer;

public class MahmoudandEhabandyetanotherxortask
{
    public static final long mod=1000000007;
    public static final int d=20;

    public static void main (String[] args) throws java.lang.Exception
    {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

        int N=sc.nextInt();
        int Q=sc.nextInt();

        int arr[]=new int[N];
        for(int i=0;i<N;i++){
            arr[i]=sc.nextInt();
        }

        int basis[][]=new int[N][d];
        int basis_size[]=new int[N];
        int size=0;
        int totalbasis[]=new int[d];
        for(int i=0;i<N;i++){
            if(insertVector(arr[i],d,totalbasis,size))
                size++;
            for(int j=0;j<d;j++){
                basis[i][j]=totalbasis[j];
            }
            basis_size[i]=size;
        }

        while(Q-->0){
            int l=sc.nextInt(),x=sc.nextInt();
            if(FindIfXinBasis(x,d,basis[l-1])){
                long ans=pow(2,l-basis_size[l-1]);
                out.println(ans);
            }
            else{
                out.println(0);
            }
        }

        out.close();
    }

    public static boolean insertVector(int vec,int d,int basis[],int size) {
        if (size == d)
            return false;

        for (int i = d - 1; i >= 0; i--) {
            if ((vec & (1 << i)) == 0) continue;
            if (basis[i] != 0) {
                vec = vec ^ basis[i];
            } else {
                basis[i] = vec;
                return true;
            }
        }
        return false;
    }

    //finding if x can represented as linear combination of the given basis
    public static boolean FindIfXinBasis(int X,int d,int basis[]) {
        for (int i = 31; i >= 0; i--) {
            if ((X & (1 << i)) == 0) continue;

            if (i >= d || basis[i] == 0)
                return false;

            X = X ^ basis[i];
        }
        return true;
    }

    //a power b
    static long pow(long a,long b){
        if(b==0)
            return 1;
        else if(b==1)
            return a;
        long ans=pow(a,b/2);
        ans=(ans*ans)%mod;
        if(b%2==1)
            ans=(ans*a)%mod;
        return ans%mod;
    }

    //-----------MyScanner class for faster input----------
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine(){
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

    }
    //--------------------------------------------------------
}
