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;
long long mod = 1e9 + 7;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return a * b / gcd(a, b); }
inline long long read() {
  long long x = 0, sign = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') sign = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return sign * x;
}
long long bit[111];
int add(long long x, int op) {
  for (long long i = 60; i >= 0; i--) {
    if ((x >> i) & 1) {
      if (bit[i])
        x ^= bit[i];
      else {
        if (op == 1) {
          bit[i] = x;
        }
        return 1;
      }
    }
  }
  return 0;
}
void Linear_basis(long long a[], int n) {
  for (long long k = 1; k <= n; k++) {
    long long x = a[k];
    for (long long i = 60; i >= 0; i--) {
      if ((x >> i) & 1) {
        if (bit[i])
          x ^= bit[i];
        else {
          bit[i] = x;
          break;
        }
      }
    }
  }
}
long long qpow(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return ans;
}
long long a[500020], ans[500020];
struct node {
  int l, x, id;
  bool operator<(const node& r) const {
    return l < r.l || (l == r.l && x < r.x);
  }
} q[500020];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  int n, t;
  cin >> n >> t;
  for (long long i = 1; i <= n; i++) cin >> a[i];
  for (long long i = 1; i <= t; i++) {
    cin >> q[i].l >> q[i].x;
    q[i].id = i;
  }
  sort(q + 1, q + 1 + t);
  int l = 1;
  int tot = 0;
  for (long long i = 1; i <= t; i++) {
    while (l <= q[i].l) {
      tot += add(a[l], 1);
      l++;
    }
    int now = add(q[i].x, 0);
    if (now == 0) {
      ans[q[i].id] = qpow(2, q[i].l - tot);
    }
  }
  for (long long i = 1; i <= t; i++) cout << ans[i] << endl;
  return 0;
}
