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;
int fastMax(int x, int y) { return (((y - x) >> (32 - 1)) & (x ^ y)) ^ y; }
int fastMin(int x, int y) { return (((y - x) >> (32 - 1)) & (x ^ y)) ^ x; }
const long long int MAXN = 1e5 + 10;
const long long int LOG_A = 21;
struct basis {
  long long int basis_v[LOG_A];
  long long int sz;
  basis() {
    for (long long int i = (0); i <= (LOG_A - 1); ++i) basis_v[i] = 0;
    sz = 0;
  }
  void insertVector(long long int mask) {
    for (long long int i = LOG_A - 1; i >= 0; i--) {
      if ((mask & (1LL << i)) == 0) continue;
      if (!basis_v[i]) {
        basis_v[i] = mask;
        ++sz;
        return;
      }
      mask ^= basis_v[i];
    }
  }
  bool can(long long int x) {
    for (long long int i = LOG_A - 1; i >= 0; i--) {
      x = min(x, (x ^ basis_v[i]));
    }
    return (x == 0);
  }
};
const long long int MOD = 1e9 + 7;
long long int power(long long int x, long long int y) {
  long long int res = 1;
  while (y) {
    if (y & 1) res = (res * x) % MOD;
    x = (x * x) % MOD;
    y >>= 1;
  }
  return res;
}
basis arr[MAXN];
void solve() {
  long long int n, q;
  cin >> n >> q;
  for (long long int i = (1); i <= (n); ++i) {
    long long int x;
    cin >> x;
    arr[i] = arr[i - 1];
    arr[i].insertVector(x);
  }
  while (q--) {
    long long int l, x;
    cin >> l >> x;
    if (arr[l].can(x) == 0)
      cout << 0 << '\n';
    else
      cout << power(2, l - arr[l].sz) << '\n';
  }
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long int t;
  t = 1;
  for (long long int i = (1); i <= (t); ++i) {
    solve();
  }
}
