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;
vector<string> split(const string& s, char c = ' ') {
  vector<string> v;
  stringstream ss(s);
  string x;
  while (getline(ss, x, c)) v.emplace_back(x);
  return move(v);
}
template <typename T, typename... Args>
inline string arrStr(T arr, int n) {
  stringstream s;
  s << "[";
  for (int i = 0; i < n - 1; i++) s << arr[i] << ",";
  s << arr[n - 1] << "]";
  return s.str();
}
inline void __evars_begin(int line) { cerr << "#" << line << ": "; }
template <typename T>
inline void __evars_out_var(vector<T> val) {
  cerr << arrStr(val, val.size());
}
template <typename T>
inline void __evars_out_var(T* val) {
  cerr << arrStr(val, 10);
}
template <typename T>
inline void __evars_out_var(T val) {
  cerr << val;
}
inline void __evars(vector<string>::iterator it) { cerr << endl; }
template <typename T, typename... Args>
inline void __evars(vector<string>::iterator it, T a, Args... args) {
  cerr << it->substr((*it)[0] == ' ', it->length()) << "=";
  __evars_out_var(a);
  cerr << "; ";
  __evars(++it, args...);
}
const long long mod = 1000000007;
const long long N = 2e6 + 2e5;
const long long M = 1e5 + 15;
long long id[N], is[N];
void caaar() {
  long long n, q;
  cin >> n >> q;
  vector<long long> v(n + 1);
  for (long long i = 1; i <= n; ++i) cin >> v[i];
  for (long long i = 0; i < N; ++i) id[i] = M;
  vector<long long> a(1);
  is[0] = 1;
  id[0] = 0;
  vector<long long> ans(n + 1);
  ans[0] = 1;
  for (long long i = 1; i <= n; ++i) {
    if (is[v[i]]) {
      ans[i] = (ans[i - 1] * 2) % mod;
    } else {
      ans[i] = ans[i - 1];
      long long sz = a.size();
      for (long long j = 0; j < sz; ++j) {
        long long t = v[i] ^ a[j];
        is[t] = 1;
        id[t] = i;
        a.push_back(t);
      }
    }
  }
  for (long long i = 0; i < q; ++i) {
    long long x, y;
    cin >> x >> y;
    if (id[y] > x)
      cout << 0 << "\n";
    else
      cout << ans[x] << "\n";
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long tc = 1;
  for (long long i = 1; i <= tc; ++i) {
    caaar();
    if (i < tc) cout << "\n";
  }
  return 0;
}
