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 A>
void rd(vector<A>& v);
template <class T>
void rd(T& x) {
  cin >> x;
}
template <class H, class... T>
void rd(H& h, T&... t) {
  rd(h);
  rd(t...);
}
template <class A>
void rd(vector<A>& x) {
  for (auto& a : x) rd(a);
}
template <typename T>
void __p(T a) {
  cout << a;
}
template <typename T, typename F>
void __p(pair<T, F> a) {
  cout << "{";
  __p(a.first);
  cout << ",";
  __p(a.second);
  cout << "}\n";
}
template <typename T>
void __p(std::vector<T> a) {
  cout << "{";
  for (auto it = a.begin(); it < a.end(); it++)
    __p(*it), cout << ",}\n"[it + 1 == a.end()];
}
template <typename T, typename... Arg>
void __p(T a1, Arg... a) {
  __p(a1);
  __p(a...);
}
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : ";
  __p(arg1);
  cout << "\n";
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  int64_t bracket = 0, i = 0;
  for (;; i++)
    if (names[i] == ',' && bracket == 0)
      break;
    else if (names[i] == '(')
      bracket++;
    else if (names[i] == ')')
      bracket--;
  const char* comma = names + i;
  cout.write(names, comma - names) << " : ";
  __p(arg1);
  cout << " | ";
  __f(comma + 1, args...);
}
void setIO(string s = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin.exceptions(cin.failbit);
  if (((int64_t)(s).size())) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
  }
}
template <int64_t MOD>
struct mint {
  static const int64_t mod = MOD;
  int64_t v;
  explicit operator int64_t() const { return v; }
  mint() { v = 0; }
  mint(long long _v) {
    v = int64_t((-MOD < _v && _v < MOD) ? _v : _v % MOD);
    if (v < 0) v += MOD;
  }
  friend bool operator==(const mint& a, const mint& b) { return a.v == b.v; }
  friend bool operator!=(const mint& a, const mint& b) { return !(a == b); }
  friend bool operator<(const mint& a, const mint& b) { return a.v < b.v; }
  mint& operator+=(const mint& m) {
    if ((v += m.v) >= MOD) v -= MOD;
    return *this;
  }
  mint& operator-=(const mint& m) {
    if ((v -= m.v) < 0) v += MOD;
    return *this;
  }
  mint& operator*=(const mint& m) {
    v = int64_t((long long)v * m.v % MOD);
    return *this;
  }
  mint& operator/=(const mint& m) { return (*this) *= inv(m); }
  friend mint power(mint a, long long p) {
    mint ans = 1;
    assert(p >= 0);
    for (; p; p /= 2, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  friend mint inv(const mint& a) {
    assert(a.v != 0);
    return power(a, MOD - 2);
  }
  mint operator-() const { return mint(-v); }
  mint& operator++() { return *this += 1; }
  mint& operator--() { return *this -= 1; }
  friend mint operator+(mint a, const mint& b) { return a += b; }
  friend mint operator-(mint a, const mint& b) { return a -= b; }
  friend mint operator*(mint a, const mint& b) { return a *= b; }
  friend mint operator/(mint a, const mint& b) { return a /= b; }
};
const int64_t MOD = 1e9 + 7;
const int64_t N = 20;
int64_t sz;
vector<int64_t> basis(N, 0);
vector<mint<MOD>> dp(1 << N);
mint<MOD> mul = 1;
void add(int64_t mask) {
  for (int64_t i = 0; i < N; i++) {
    if ((mask & (int64_t(1) << i)) == 0) continue;
    if (!basis[i]) {
      basis[i] = mask;
      ++sz;
      return;
    }
    mask ^= basis[i];
  }
}
void upd(int64_t mask) {
  vector<mint<MOD>> dp2(1 << N);
  for (int64_t i = int64_t(0); i < int64_t(1 << N); ++i) dp[i] *= mul;
  mul = 1;
  for (int64_t i = int64_t(0); i < int64_t(1 << N); ++i)
    dp2[i] = dp[i] + dp[i ^ mask];
  for (int64_t i = int64_t(0); i < int64_t(1 << N); ++i) dp[i] = dp2[i];
  return;
}
signed main() {
  setIO();
  int64_t n, q;
  rd(n, q);
  vector<int64_t> a(n);
  rd(a);
  vector<array<int64_t, 3>> queries;
  for (int64_t i = int64_t(0); i < int64_t(q); ++i) {
    int64_t l, x;
    rd(l, x);
    --l;
    queries.push_back({l, x, i});
  }
  sort((queries).begin(), (queries).end());
  dp[0] = 1;
  vector<int64_t> ans(q);
  int64_t cur = -1;
  for (auto [l, x, Q] : queries) {
    while (cur < l) {
      int64_t cache = sz;
      add(a[++cur]);
      if (sz != cache) {
        upd(a[cur]);
      } else {
        mul *= 2;
      }
    }
    mint<MOD> temp = dp[x] * mul;
    ans[Q] = temp.v;
  }
  for (auto i : ans) cout << i << "\n";
}
