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.
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f, oo = inf;
char __wzp[1 << 15 | 1], *__S = __wzp + 32768;
inline long long read() {
  register long long x = 0;
  char f = 0;
  register char c =
      (__S >= __wzp + 32768
       ? (__wzp[fread(__wzp, sizeof(char), 1 << 15, stdin)] = EOF),
       *((__S = __wzp)++) : *(__S++));
  for (; !isdigit(c);
       c = (__S >= __wzp + 32768
            ? (__wzp[fread(__wzp, sizeof(char), 1 << 15, stdin)] = EOF),
            *((__S = __wzp)++) : *(__S++)))
    f |= (c == '-');
  for (; isdigit(c);
       c = (__S >= __wzp + 32768
            ? (__wzp[fread(__wzp, sizeof(char), 1 << 15, stdin)] = EOF),
            *((__S = __wzp)++) : *(__S++)))
    x = (x << 1) + (x << 3) + (c ^ 48);
  return f ? -x : x;
}
inline double readdb() {
  register double x = 0, p = 0.1;
  register char f = 0,
                c = (__S >= __wzp + 32768
                     ? (__wzp[fread(__wzp, sizeof(char), 1 << 15, stdin)] =
                            EOF),
                     *((__S = __wzp)++) : *(__S++));
  for (; !isdigit(c);
       c = (__S >= __wzp + 32768
            ? (__wzp[fread(__wzp, sizeof(char), 1 << 15, stdin)] = EOF),
            *((__S = __wzp)++) : *(__S++)))
    f |= (c == '-');
  for (; isdigit(c);
       c = (__S >= __wzp + 32768
            ? (__wzp[fread(__wzp, sizeof(char), 1 << 15, stdin)] = EOF),
            *((__S = __wzp)++) : *(__S++)))
    x = x * 10 + (c ^ 48);
  if (c == '.')
    for (c = (__S >= __wzp + 32768
              ? (__wzp[fread(__wzp, sizeof(char), 1 << 15, stdin)] = EOF),
              *((__S = __wzp)++) : *(__S++));
         isdigit(c);
         c = (__S >= __wzp + 32768
              ? (__wzp[fread(__wzp, sizeof(char), 1 << 15, stdin)] = EOF),
              *((__S = __wzp)++) : *(__S++)),
        p /= 10)
      x = x + (c ^ 48) * p;
  return f ? -x : x;
}
inline void write(long long x) {
  if (x < 0) x = -x, putchar('-');
  if (x >= 10) write(x / 10);
  putchar(x % 10 + '0');
}
inline void writeln(long long x) {
  write(x);
  puts("");
}
inline void writeln(long long x, char c, long long y) {
  write(x);
  putchar(c);
  writeln(y);
}
inline void writeln(long long x, char c, long long y, char d, long long z) {
  write(x);
  putchar(c);
  write(y);
  putchar(d);
  writeln(z);
}
const int Mod = 1e9 + 7;
const int ppow(int a, int b) {
  int ans = 1;
  for (; b; b >>= 1, a = 1ll * a * a % Mod)
    if (b & 1) ans = 1ll * ans * a % Mod;
  return ans;
}
const int maxn = 100005;
int n, Q;
struct DS {
  int a[21], tot;
  DS() {
    memset(a, 0, sizeof(a));
    tot = 0;
  }
  void add(int x) {
    for (int i = 20; i >= 0; i--) {
      if (x >> i & 1) {
        if (!a[i]) {
          a[i] = x;
          return;
        } else
          x ^= a[i];
      }
    }
    ++tot;
  }
  int query(int x) {
    for (int i = 20; i >= 0; i--) {
      if (x >> i & 1) {
        if (!a[i]) {
          return 0;
        } else
          x ^= a[i];
      }
    }
    return ppow(2, tot);
  }
} T[maxn];
int main() {
  n = read(), Q = read();
  for (register int i = (1); i <= (n); ++i) {
    T[i] = T[i - 1];
    T[i].add(read());
  }
  while (Q--) {
    int pos = read(), x = read();
    writeln(T[pos].query(x));
  }
  return 0;
}
