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 long long ts = 100005;
const long long mod = 1000000007;
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  ;
  int n, M;
  cin >> n >> M;
  int rel[ts * 2], a[ts * 2];
  vector<pair<pair<int, int>, int> > q;
  set<int> s;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= M; i++) {
    int a, b;
    cin >> a >> b;
    q.push_back(make_pair(make_pair(a, b), i));
  }
  sort(q.begin(), q.end());
  s.insert(0);
  int ans = 1;
  for (int j = 1; j <= q[0].first.first; j++) {
    int m = a[j];
    if (s.count(m))
      ans *= 2, ans %= mod;
    else {
      set<int> S(s);
      for (int u : S) s.insert(u ^ m);
    }
    int pos = q[0].second;
    int val = q[0].first.second;
    rel[pos] = (s.count(val) == 1) ? ans : 0;
  }
  int j = 0;
  while (j < M - 1) {
    for (int i = q[j].first.first + 1; i <= q[j + 1].first.first; i++) {
      int m = a[i];
      if (s.count(m))
        ans *= 2, ans %= mod;
      else {
        set<int> S(s);
        for (int u : S) {
          s.insert(u ^ m);
        }
      }
    }
    int pos = q[j + 1].second;
    int val = q[j + 1].first.second;
    if (!s.count(val))
      rel[pos] = 0;
    else
      rel[pos] = ans;
    j++;
  }
  for (int i = 1; i <= M; i++) cout << rel[i] << endl;
}
