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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Vector;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Rene
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskF solver = new TaskF();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskF {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int queries = in.nextInt();
            int[] dim = new int[n];
            Vector<BasisVector> basis = new Vector<>();
            for (int i = 0; i < n; i++) {
                int a = in.nextInt();
                int d = i > 0 ? dim[i - 1] : 0;
                int p = project(a, basis, d);
                if (p != 0) {
                    dim[i] = d + 1;
                    basis.add(new BasisVector(p, Integer.numberOfTrailingZeros(p)));
                } else dim[i] = d;
            }
            for (int i = 0; i < queries; i++) {
                int l = in.nextInt();
                int x = in.nextInt();
                int p = project(x, basis, dim[l - 1]);
                long result = p == 0 ? modPow(2, l - dim[l - 1], 1_000_000_007L) : 0;
                out.println(result);
            }
        }

        long modPow(long a, long b, long mod) {
            long result = 1L;
            while (b > 0) {
                if (b % 2 == 1) {
                    b--;
                    result = (result * a) % mod;
                } else {
                    a = (a * a) % mod;
                    b /= 2;
                }
            }
            return result;
        }

        int project(int vec, Vector<BasisVector> basis, int dim) {
            for (int i = 0; i < dim; i++) {
                BasisVector v = basis.get(i);
                if (((1L << v.index) & vec) != 0) vec ^= v.vec;
            }
            return vec;
        }

        class BasisVector {
            int vec;
            int index;

            BasisVector(int v, int i) {
                vec = v;
                index = i;
            }

        }

    }

    static class InputReader implements InputInterface {
        public InputStream stream;
        private int current;
        private int size;
        private byte[] buffer = new byte[10000];

        public InputReader(InputStream stream) {
            this.stream = stream;
            current = 0;
            size = 0;
        }

        public InputReader() {
        }

        int read() {
            int result;
            try {
                if (current >= size) {
                    current = 0;
                    size = stream.read(buffer);
                    if (size < 0) return -1;
                }
            } catch (IOException e) {
                throw new RuntimeException();
            }
            return buffer[current++];
        }


        public int nextInt() {
            int sign = 1;
            int result = 0;
            int c = readNextValid();
            if (c == '-') {
                sign = -1;
                c = read();
            }
            do {
                if (c < '0' || c > '9') throw new RuntimeException();
                result = 10 * result + c - '0';
                c = read();
            } while (!isEmpty(c));
            result *= sign;
            return result;
        }

        private int readNextValid() {
            int result;
            do {
                result = read();
            } while (isEmpty(result));
            return result;
        }

        private boolean isEmpty(int c) {
            return c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == -1;
        }

    }

    static interface InputInterface {
    }
}

