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;
class Solution {
 public:
  Solution(vector<int>& _A, int n) : nums(_A), N(n), p(0) {
    seqs.clear();
    seqs.insert(0);
    cnts.clear();
    cnts.resize(n + 1, 0);
    cnts[0] = 1;
    time[0] = 0;
    tmp.clear();
    tmp.resize(1001000, 0);
  }
  int query(int l, int x) {
    if (l <= 0) {
      return 0;
    }
    l = min(l, N);
    while (p < l) {
      int a = nums[p];
      if (seqs.count(a) > 0) {
        cnts[p + 1] = addM(cnts[p], cnts[p]);
      } else {
        int size = 0;
        for (auto num : seqs) {
          tmp[size++] = num ^ a;
        }
        for (int i = 0; i < size; ++i) {
          time[tmp[i]] = p + 1;
          seqs.insert(tmp[i]);
        }
        cnts[p + 1] = cnts[p];
      }
      ++p;
    }
    int a = nums[l - 1];
    int at = time[a];
    auto it = time.find(x);
    if (at < l) {
      if (it != time.end() && it->second < l) {
        return cnts[l];
      } else {
        return 0;
      }
    } else {
      if (it != time.end() && it->second < l) {
        return cnts[l];
      } else {
        auto it2 = time.find(x ^ a);
        if (it2 != time.end() && it2->second < l) {
          return cnts[l];
        } else {
          return 0;
        }
      }
    }
    return 0;
  }

 private:
  int N;
  int p;
  vector<int> nums;
  set<int> seqs;
  vector<int> cnts;
  vector<int> tmp;
  map<int, int> time;
  const int M = 1e9 + 7;
  long long addM(long long a, long long b) {
    a += b;
    a %= M;
    if (a < 0) {
      a += M;
    }
    return a;
  }
};
int main(int argc, char** argv) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<int> nums(n);
  for (int i = 0; i < n; ++i) {
    cin >> nums[i];
  }
  Solution sol(nums, n);
  for (int i = 0, l = 0, x = 0; i < q; ++i) {
    cin >> l >> x;
    cout << sol.query(l, x) << endl;
  }
  return 0;
}
