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;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline long long rand(long long x, long long y) {
  return rng() % (y + 1 - x) + x;
}
string inline to_string(char c) {
  string second(1, c);
  return second;
}
template <typename T>
inline T gcd(T a, T b) {
  return a == 0 ? llabs(b) : gcd(b % a, a);
}
using ll = long long;
using ld = long double;
using pi = pair<ll, ll>;
using spi = pair<ll, pi>;
using dpi = pair<pi, pi>;
ll n, q, R[(100006)];
pi bit[20];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> q;
  auto add = [&](ll x, ll ind) {
    for (ll i = 0; i <= ll(19); ++i)
      if (1 << i & x) {
        if (bit[i].first) {
          x ^= bit[i].first;
          continue;
        }
        bit[i] = pi(x, ind);
        return 1;
      }
    return 0;
  };
  ll mod = 1e9 + 7;
  R[0] = 1;
  for (ll i = 1; i <= ll(n); ++i) {
    ll x;
    cin >> x;
    R[i] = R[i - 1] * (add(x, i) ? 1 : 2) % mod;
  }
  for (ll ii = 1; ii <= ll(q); ++ii) {
    ll l, x;
    cin >> l >> x;
    for (ll i = 0; i <= ll(19); ++i)
      if (1 << i & x) {
        if (bit[i].first == 0 || bit[i].second > l) {
          break;
        }
        x ^= bit[i].first;
      }
    cout << (x ? 0 : R[l]) << '\n';
  }
}
