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;
template <class C>
void min_self(C &a, C b) {
  a = min(a, b);
}
template <class C>
void max_self(C &a, C b) {
  a = max(a, b);
}
long long mod(long long n, long long m = 1000000007) {
  n %= m, n += m, n %= m;
  return n;
}
const int MAXN = 1e5 + 5;
const int LOGN = 21;
const long long INF = 1e14;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
long long expo(long long base, long long exp, long long m = 1000000007) {
  long long res = 1;
  while (exp > 0) {
    if (exp & 1) {
      res *= base;
      res = mod(res, m);
    }
    base *= base;
    base = mod(base, m);
    exp /= 2;
  }
  res = mod(res, m);
  return res;
}
int now[MAXN], sz, n, q, k;
pair<int, int> basis[32];
bool insert(int val, int ind) {
  for (int i = 0; i < k; i++) {
    if (((1 << i) & val) == 0) continue;
    if (!basis[i].first) {
      basis[i] = {val, ind};
      sz++;
      return 1;
    }
    val ^= basis[i].first;
  }
  return 0;
}
bool check(int val, int ind) {
  for (int i = 0; i < k; i++) {
    if (((1 << i) & val) == 0) continue;
    if (basis[i].second > ind || basis[i].first == 0) {
      return 0;
    }
    val ^= basis[i].first;
  }
  return 1;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  k = 21;
  sz = 0;
  for (int i = 0; i < k; i++) basis[i] = {0, 0};
  cin >> n >> q;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (i) now[i] = now[i - 1];
    if (insert(x, i)) {
      now[i]++;
    }
  }
  while (q--) {
    int l, x;
    cin >> l >> x;
    l--;
    if (check(x, l))
      cout << expo(2, l + 1 - now[l]), cout << "\n";
    else
      cout << 0, cout << "\n";
  }
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}
