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.text.DecimalFormat;
import java.util.*;
import java.io.*;

public class Main {
    private static final int mod = 1000000007;

    public static void main(String[] args) throws Exception{
        IO io = new IO(null,null);
        int n = io.getNextInt(),m = io.getNextInt();
        int [] A = new int[n];
        for (int i = 0;i < n;i++)
            A[i] = io.getNextInt();

        int [] Q = new int[m];
        int [] ans = new int[m];
        int [] K = new int[m];
        ArrayList<Integer> ord = new ArrayList<>(m);
        for (int i = 0;i < m;i++) {
            Q[i] = io.getNextInt();
            K[i] = io.getNextInt();
            ord.add(i);
        }
        Collections.sort(ord, new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return Q[a] - Q[b];
            }
        });

        ArrayList<val> C = new ArrayList<>();
        int fulfilled = 0,p2 = 1,i = 0;
        int [] freq = new int[1 << 20];
        freq[0] = 1;


        for (int q : ord) {
            for (;i < Q[q];i++) {
                int x = A[i];
                val aux = new val(x);
                int msb = aux.msb;

                for (val c : C) {
                    if (x == 0) break;
                    if (msb > c.msb) break;
                    if (msb == c.msb)
                        x ^= c.x;
                    while (msb >= 0 && ((x >> msb) & 1) == 0) msb--;
                }
                if (x == 0) {
                    p2 <<= 1;
                    if (p2 >= mod) p2 -= mod;
                }
                else {
                    for (int msk = 0,L = 1 << C.size();msk < L;msk++) {
                        int v = x;
                        for (int j = 0;j < C.size();j++)
                            if ((msk & (1 << j)) != 0)
                                v ^= C.get(j).x;
                        freq[v]++;
                    }
                    C.add(new val(x));
                    Collections.sort(C);
                }
            }
//            System.err.println(C);
            ans[q] = (int)((freq[K[q]] * (long)p2)%mod);
        }

        for (int q = 0;q < m;q++)
            io.println(ans[q]);
        io.close();
    }


}

class val implements Comparable<val>{
    int x,msb;
    public val(int y) {
        x = y;
        for (int i = 0;i < 20 && y > 0;i++)
            if ((y & (1 << i)) != 0) {
                msb = i;
                y ^= 1 << i;
            }
    }
    @Override
    public int compareTo(val o) {
        return -(x - o.x);
    }
    @Override
    public String toString(){
        return "(" + x + ", " + msb + ")";
    }
}

class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public boolean hasMore() throws IOException{
        if(st != null && st.hasMoreTokens()) return true;
        if(br != null && br.ready()) return true;
        return false;
    }

    public String getNext() throws FileNotFoundException, IOException{
        while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public String getNextLine() throws FileNotFoundException, IOException{
        return br.readLine().trim();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }
    public long getNextLong() throws FileNotFoundException, IOException{
        return Long.parseLong(getNext());
    }

    public void print(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f" ,x);
    }
    public void println(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f\n" ,x);
    }
    public void print(Object o) throws  IOException{
        writer.print(o.toString());
    }

    public void println(Object o) throws  IOException{
        writer.println(o.toString());
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
    public void outputArr(Object [] A) throws IOException{
        int L = A.length;
        for (int i = 0;i < L;i++) {
            if(i > 0) writer.print(" ");
            writer.print(A[i]);
        }
        writer.print("\n");
    }
}
