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 N = 100010, M = 1000010, P = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int INF = 0xcfcfcfcf;
const double eps = 1e-9, pi = asin(1) * 2;
inline long long read();
inline int ADD(int a, int b) { return a + b >= P ? a + b - P : a + b; }
inline int MINUS(int a, int b) { return a - b < 0 ? a - b + P : a - b; }
inline int quickmi(int x, int n) {
  int res = 1;
  for (; n; n >>= 1) {
    if (n & 1) res = (1ll * res * (x)) % P;
    x = (1ll * x * (x)) % P;
  }
  return res;
}
int n, q;
int a[N];
struct XXJ {
  int a[N];
  inline bool insert(int x) {
    for (int i = 20; i >= 0; i--) {
      if (x & (1 << i)) {
        if (!a[i]) {
          a[i] = x;
          return true;
        } else
          x ^= a[i];
      }
    }
    return false;
  }
  inline bool query(int x) {
    for (int i = 20; i >= 0; i--) x = min(x, x ^ a[i]);
    return !x;
  }
} xxj;
struct QUESTIONS {
  int l, x, id;
} ques[N];
inline bool operator<(const QUESTIONS &a, const QUESTIONS &b) {
  return a.l < b.l;
}
int ans[N];
inline long long read() {
  long long s = 0;
  bool flag = false;
  char ch = getchar();
  for (; ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') flag = true;
  for (; '0' <= ch && ch <= '9'; ch = getchar())
    s = (s << 3) + (s << 1) + (ch ^ '0');
  if (flag) return -s;
  return s;
}
int main() {
  n = read(), q = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  for (int i = 1; i <= q; i++)
    ques[i].l = read(), ques[i].x = read(), ques[i].id = i;
  sort(ques + 1, ques + q + 1);
  int cnt = 0;
  for (int i = 1; i <= q; i++) {
    for (int j = ques[i - 1].l + 1; j <= ques[i].l; j++)
      cnt += xxj.insert(a[j]);
    ans[ques[i].id] = xxj.query(ques[i].x) * quickmi(2, ques[i].l - cnt);
  }
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
  return 0;
}
