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 F473 {
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        int n = sc.nextInt(); int q = sc.nextInt();
        int [] a = new int[n + 1];
        for (int i = 1; i <= n; i++) a[i] = sc.nextInt();
        ArrayList<Query> queries = new ArrayList<>();
        for (int i = 0; i < q; i++) {
            Query qq = new Query(sc.nextInt(), sc.nextInt());
            qq.i = i;
            queries.add(qq);
        }
        Collections.sort(queries, Comparator.comparingInt(x -> x.l));
        int cur = 0; int pow = 0;
        long [] res = new long[q];
        Set<Integer> set = new HashSet<>();
        set.add(0);
        for (int i = 1; i <= n; i++) {
            if (set.contains(a[i])) ++pow;
            else {
                Set<Integer> ns = new HashSet<>();
                for (Integer j: set) {
                    ns.add(j);
                    ns.add(a[i] ^ j);
                }
                set = ns;
            }
            while (cur < q && i == queries.get(cur).l) {
                if (queries.get(cur).i == 0) {
                    System.out.println();
                }
                if (set.contains(queries.get(cur).xor)) {
                    res[queries.get(cur).i] = pow(2, pow);
                } else res[queries.get(cur).i] = 0;
                ++cur;
            }
        }
        for (int i = 0; i < q; i++) out.println(res[i]);
        out.close();
    }

    static long[] fac;
    static long mod = (long) 1e9 + 7;

    static void initFac(long n) {
        fac = new long[(int)n + 1];
        fac[0] = 1;
        for (int i = 1; i <= n; i++) {
            fac[i] = (fac[i - 1]  * i) % mod;
        }
    }



    static long nck(int n, int k) {
        if (n < k)
            return 0;
        long den = inv((int) (fac[k] * fac[n - k] % mod));
        return fac[n] * den % mod;
    }

    static long pow(long b, long e) {
        long ans = 1;
        while (e > 0) {
            if (e % 2 == 1)
                ans = ans * b % mod;
            e >>= 1;
            b = b * b % mod;
        }
        return ans;
    }

    static long inv(long x) {
        return pow(x, mod - 2);
    }

    static class Query {
        int l; int xor; int i;
        Query(int l, int xor) {
            this.l = l; this.xor = xor;
        }
    }


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

        public MyScanner() {
            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;
        }


    }

}