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 T, class U>
void ckmin(T &a, U b) {
  if (a > b) a = b;
}
template <class T, class U>
void ckmax(T &a, U b) {
  if (a < b) a = b;
}
const int INF = 1e9 + 7;
const int MAXN = 1e5 + 13;
int add(int a, int b) {
  a += b;
  if (a >= INF) a -= INF;
  return a;
}
int mul(int a, int b) { return (long long)a * b % INF; }
int sub(int a, int b) {
  a -= b;
  if (a < 0) a += INF;
  return a;
}
int pwr(int a, int b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) res = mul(res, a);
    b >>= 1;
    a = mul(a, a);
  }
  return res;
}
int inv(int a) { return pwr(a, INF - 2); }
int dvd(int a, int b) { return mul(a, inv(b)); }
int N, Q, B;
int arr[MAXN];
vector<pair<int, int> > queries[MAXN];
int pw2[MAXN];
int ans[MAXN];
int basis[23];
int32_t main() {
  cout << fixed << setprecision(12);
  cerr << fixed << setprecision(4);
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> Q;
  pw2[0] = 1;
  for (auto i = (0); i < (N); i++) {
    pw2[i + 1] = add(pw2[i], pw2[i]);
  }
  for (auto i = (0); i < (N); i++) {
    cin >> arr[i];
  }
  for (auto i = (0); i < (Q); i++) {
    int l, x;
    cin >> l >> x;
    queries[l - 1].push_back({x, i});
  }
  for (auto i = (0); i < (N); i++) {
    int x = arr[i];
    for (auto j = (20) - 1; j >= (0); j--) {
      if (!(x & (1 << j))) continue;
      if (basis[j] == 0) {
        basis[j] = x;
        B++;
        break;
      }
      x = min(x, x ^ basis[j]);
    }
    for (pair<int, int> p : queries[i]) {
      int x = p.first;
      for (auto j = (20) - 1; j >= (0); j--) {
        if (!(x & (1 << j))) continue;
        if (basis[j] == 0) continue;
        x = min(x, x ^ basis[j]);
      }
      if (x != 0) {
        ans[p.second] = 0;
        continue;
      }
      ans[p.second] = pw2[i + 1 - B];
    }
  }
  for (auto i = (0); i < (Q); i++) {
    cout << ans[i] << '\n';
  }
}
