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 int mod = 1e9 + 7;
struct base {
  static vector<int> pow2;
  int d[22 + 1] = {}, p[22 + 1] = {};
  int sz = 0, cnt = 0, ins = 0;
  bool insert(int x) {
    if (pow2.size() <= ++ins) pow2.push_back((pow2.back() << 1) % mod);
    for (int i = 22; ~i; i--)
      if ((x >> i) & 1) {
        if (!d[i]) {
          cnt++, d[i] = x;
          break;
        }
        x ^= d[i];
      }
    if (x) p[sz++] = x;
    return x;
  }
  int max() {
    int ret = 0;
    for (int i = 22; ~i; i--)
      if ((ret ^ d[i]) > ret) ret ^= d[i];
    return ret;
  }
  int min() {
    for (int i = 0; i <= 22; i++)
      if (d[i]) return d[i];
    return 0;
  }
  int count(int x) {
    for (int i = 22; ~i; i--)
      if ((x >> i) & 1) x ^= d[i];
    return x ? 0 : pow2[ins - sz];
  }
};
vector<int> base::pow2{1};
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  vector<int> a(n);
  for (int& i : a) scanf("%d", &i);
  vector<pair<int, int>> qs[n];
  for (int l, x, i = 0; i < q; i++) {
    scanf("%d%d", &l, &x);
    qs[l - 1].push_back({x, i});
  }
  base b;
  vector<int> ans(q);
  for (int i = 0; i < n; i++) {
    b.insert(a[i]);
    for (auto& p : qs[i]) ans[p.second] = b.count(p.first);
  }
  for (int& a : ans) printf("%d\n", a);
}
