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;
void readi(int &x) {
  int v = 0, f = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = v * 10 + c - '0';
  while (isdigit(c = getchar())) v = v * 10 + c - '0';
  x = v * f;
}
void readll(long long &x) {
  long long v = 0ll, f = 1ll;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = v * 10 + c - '0';
  while (isdigit(c = getchar())) v = v * 10 + c - '0';
  x = v * f;
}
void readc(char &x) {
  char c;
  while ((c = getchar()) == ' ')
    ;
  x = c;
}
void writes(string s) { puts(s.c_str()); }
void writeln() { writes(""); }
void writei(int x) {
  if (!x) putchar('0');
  char a[25];
  int top = 0;
  while (x) {
    a[++top] = (x % 10) + '0';
    x /= 10;
  }
  while (top) {
    putchar(a[top]);
    top--;
  }
}
void writell(long long x) {
  if (!x) putchar('0');
  char a[25];
  int top = 0;
  while (x) {
    a[++top] = (x % 10) + '0';
    x /= 10;
  }
  while (top) {
    putchar(a[top]);
    top--;
  }
}
inline long long inc(int &x) { return ++x; }
inline long long inc(long long &x) { return ++x; }
inline long long inc(int &x, long long y) { return x += y; }
inline long long inc(long long &x, long long y) { return x += y; }
inline double inc(double &x, double y) { return x += y; }
inline long long dec(int &x) { return --x; }
inline long long dec(long long &x) { return --x; }
inline long long dec(int &x, long long y) { return x -= y; }
inline long long dec(long long &x, long long y) { return x -= y; }
inline double dec(double &x, double y) { return x -= y; }
inline long long mul(int &x) { return x = ((long long)x) * x; }
inline long long mul(long long &x) { return x = x * x; }
inline long long mul(int &x, long long y) { return x *= y; }
inline long long mul(long long &x, long long y) { return x *= y; }
inline double mul(double &x, double y) { return x *= y; }
inline long long divi(int &x) { return x = sqrt(x); }
inline long long divi(long long &x) { return x = sqrt(x); }
inline long long divi(int &x, long long y) { return x /= y; }
inline long long divi(long long &x, long long y) { return x /= y; }
inline double divi(double &x, double y) { return x /= y; }
inline long long mod(int &x, long long y) { return x %= y; }
inline long long mod(long long &x, long long y) { return x %= y; }
struct bse {
  long long d[25], p[25], cnt;
  void insert(long long x) {
    long long i;
    for (i = 20; i >= 0; i--) {
      if ((1ll << i) & x) {
        if (!d[i]) {
          d[i] = x;
          cnt++;
        }
        x ^= d[i];
      }
    }
  }
  bool check(long long x) {
    long long i;
    for (i = 20; i >= 0; i--) {
      if ((1ll << i) & x) {
        x ^= d[i];
      }
    }
    return x == 0;
  }
} d;
long long n, m, i, j, a[123456], p = 1e9 + 7;
struct qq {
  long long x, l, id, ans;
} q[123456];
bool cmp(qq x, qq y) { return x.l < y.l; }
bool cmp2(qq x, qq y) { return x.id < y.id; }
long long qp(long long x, long long y) {
  if (y < 0) return 0;
  if (y == 0) return 1;
  if (y == 1) return x;
  long long z = qp(x, y / 2);
  mul(z);
  mod(z, p);
  if (y & 1) {
    mul(z, x);
    mod(z, p);
  }
  return z;
}
int main() {
  ios_base::sync_with_stdio(false);
  ;
  cin >> n >> m;
  if ((1) <= ((n)))
    for (((i)) = (1); ((i)) <= ((n)); ((i))++) cin >> a[i];
  if ((1) <= ((m)))
    for (((i)) = (1); ((i)) <= ((m)); ((i))++) {
      cin >> q[i].l >> q[i].x;
      q[i].id = i;
      q[i].ans = 0;
    }
  stable_sort(q + 1, q + m + 1, cmp);
  q[0].l = 0;
  for (i = 1; i <= m; i++) {
    if ((q[i - 1].l) <= (q[i].l))
      for ((j) = (q[i - 1].l); (j) <= (q[i].l); (j)++) d.insert(a[j]);
    if (d.check(q[i].x)) q[i].ans = qp(2, (q[i].l - d.cnt));
  }
  stable_sort(q + 1, q + m + 1, cmp2);
  if ((1) <= ((m)))
    for (((i)) = (1); ((i)) <= ((m)); ((i))++) cout << q[i].ans << endl;
  return 0;
}
