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;
using ll = long long;
using ld = long double;
const ll MOD = 1e9 + 7, INF = 2e18, hell = 998244353;
ld st;
const int mod = 1e9 + 7, inf = 2e9;
int tests = 1;
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll x = -INF, ll y = INF) {
  return uniform_int_distribution<ll>(x, y)(rng);
}
void preprocess();
void run_test();
int main() {
  ios::sync_with_stdio(0);
  cout.tie(0);
  cin.tie(0);
  cout << fixed << setprecision(10);
  preprocess();
  for (int i = 1; i <= tests; ++i) {
    if (!1) cerr << "While solving TC " << i << ":\n", st = clock();
    run_test();
    if (!1)
      cerr << "TC " << i
           << " done in:: " << 1000 * (clock() - st) / CLOCKS_PER_SEC
           << " ms\n";
  }
  if (!1)
    cerr << "\nGG in: " << 1000 * ((ld)clock()) / CLOCKS_PER_SEC << " ms\n";
  return 0;
}
const int N = 1e5 + 1;
int n;
int arr[N];
void preprocess() {}
struct mi {
  using T = decay<decltype(MOD)>::type;
  T v;
  explicit operator T() const { return v; }
  mi() { v = 0; }
  mi(ll _v) {
    v = (-MOD < _v && _v < MOD) ? _v : _v % MOD;
    if (v < 0) v += MOD;
  }
  friend bool operator==(const mi& a, const mi& b) { return a.v == b.v; }
  friend bool operator!=(const mi& a, const mi& b) { return !(a == b); }
  friend bool operator<(const mi& a, const mi& b) { return a.v < b.v; }
  friend ostream& operator<<(ostream& os, const mi& a) { return os << a.v; }
  mi& operator+=(const mi& m) {
    if ((v += m.v) >= MOD) v -= MOD;
    return *this;
  }
  mi& operator-=(const mi& m) {
    if ((v -= m.v) < 0) v += MOD;
    return *this;
  }
  mi& operator*=(const mi& m) {
    v = (ll)v * m.v % MOD;
    return *this;
  }
  mi& operator/=(const mi& m) { return (*this) *= inv(m); }
  friend mi pow(mi a, ll p) {
    mi ans = 1;
    assert(p >= 0);
    for (; p; p /= 2, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  friend mi inv(const mi& a) {
    assert(a.v != 0);
    return pow(a, MOD - 2);
  }
  mi operator-() const { return mi(-v); }
  mi& operator++() { return *this += 1; }
  mi& operator--() { return *this -= 1; }
  friend mi operator+(mi a, const mi& b) { return a += b; }
  friend mi operator-(mi a, const mi& b) { return a -= b; }
  friend mi operator*(mi a, const mi& b) { return a *= b; }
  friend mi operator/(mi a, const mi& b) { return a /= b; }
};
void run_test() {
  int n, q;
  cin >> n >> q;
  int a[n];
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  vector<pair<int, int>> xid[n + 1];
  for (int i = 0; i < q; ++i) {
    int l, x;
    cin >> l >> x;
    xid[l - 1].emplace_back(x, i);
  }
  mi ans[q];
  mi two = 2;
  set<int> dp;
  dp.insert(0);
  for (int i = 0; i < n; ++i) {
    if (dp.count(a[i]) == 0) {
      vector<int> add;
      for (auto& z : dp) add.push_back(z ^ a[i]);
      for (auto& z : add) dp.insert(z);
    }
    for (auto u : xid[i]) {
      if (dp.count(u.first)) {
        ans[u.second] = pow(two, i + 1) / ((int)dp.size());
      } else
        ans[u.second] = 0;
    }
  }
  for (int i = 0; i < q; ++i) {
    cout << ans[i] << endl;
  }
};
