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;
const double PI = acos(-1);
const double epsilon = 1e-7;
inline void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
}
vector<long long> v;
vector<long long> dp;
set<long long> xors;
class node {
 public:
  long long l, x, index;
  node(long long l, long long x, long long index) {
    this->l = l;
    this->x = x;
    this->index = index;
  }
  bool operator<(node& that) {
    if (this->l < that.l)
      return true;
    else
      return false;
  }
};
void solve(long long from, long long l, vector<node>& query,
           vector<pair<long long, long long>>& ans) {
  long long i = from;
  long long j = i + 1;
  while (i < l) {
    if (xors.find(v[i]) != xors.end()) {
      dp[j] = (2 * dp[j - 1]) % 1000000007;
    } else {
      dp[j] = dp[j - 1] % 1000000007;
      stack<long long> s;
      for (auto e : xors) s.push(e ^ v[i]);
      while (!s.empty()) {
        xors.insert(s.top());
        s.pop();
      }
    }
    i++;
    j++;
  }
  i = l;
  j = l + 1;
  long long res;
  for (auto q : query) {
    long long x = q.x;
    long long index = q.index;
    if (xors.find(v[i]) != xors.end()) {
      if (xors.find(x) != xors.end()) {
        res = (2 * dp[j - 1]) % 1000000007;
        ans.push_back({index, res});
      } else {
        res = 0;
        ans.push_back({index, res});
      }
    } else {
      if (xors.find(x) != xors.end()) {
        res = dp[j - 1] % 1000000007;
        ans.push_back({index, res});
      } else {
        if (xors.find((v[i] ^ x)) != xors.end()) {
          res = dp[j - 1] % 1000000007;
          ans.push_back({index, res});
        } else {
          ans.push_back({index, 0});
        }
      }
    }
  }
  if (xors.find(v[i]) != xors.end()) {
    dp[j] = (2 * dp[j - 1]) % 1000000007;
  } else {
    dp[j] = dp[j - 1] % 1000000007;
    stack<long long> s;
    for (auto e : xors) s.push(e ^ v[i]);
    while (!s.empty()) {
      xors.insert(s.top());
      s.pop();
    }
  }
}
signed main(void) {
  fastIO();
  long long n, q;
  cin >> n >> q;
  v.resize(n);
  dp.resize(n + 1, 0);
  dp[0] = 1;
  for (int i = 0; i < n; i++) cin >> v[i];
  vector<pair<long long, long long>> ans;
  vector<vector<node>> queries(n);
  long long start = 0;
  long long index = 0;
  xors.insert(0);
  while (q-- > 0) {
    long long l, x;
    cin >> l >> x;
    l--;
    queries[l].push_back(node(l, x, index++));
  }
  for (int i = 0; i < n; i++) {
    if (queries.size() > 0) {
      solve(start, i, queries[i], ans);
      start = i + 1;
    }
  }
  sort(ans.begin(), ans.end());
  for (auto e : ans) cout << e.second << '\n';
  return 0;
}
