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;
inline long long read() {
  long long x = 0, f = 1, ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) write(x / 10);
  putchar(x % 10 + '0');
}
inline void writeln(long long x) {
  write(x);
  puts("");
}
const long long N = 1e5 + 5, mod = 1e9 + 7;
long long n, q, sum[N], f[N][30];
inline long long insert(long long *g, long long x) {
  for (long long i = 30; i >= 0; i--) {
    if (x & (1ll << i)) {
      if (!g[i]) {
        g[i] = x;
        return 1;
      } else
        x ^= g[i];
    }
  }
  return 0;
}
inline void init() {
  n = read();
  q = read();
  for (long long i = 1; i <= n; i++) {
    for (long long j = 0; j <= 30; j++) f[i][j] = f[i - 1][j];
    sum[i] = sum[i - 1] + insert(f[i], read());
  }
}
inline long long Pow(long long x, long long k) {
  long long y = 1;
  for (; k; x = x * x % mod, k >>= 1)
    if (k & 1) y = y * x % mod;
  return y;
}
inline bool check(long long l, long long x) {
  for (long long i = 30; i >= 0; i--) {
    if (x & (1ll << i)) x ^= f[l][i];
  }
  return x == 0;
}
inline void solve() {
  while (q--) {
    long long l = read(), x = read();
    writeln(check(l, x) ? Pow(2, l - sum[l]) : 0);
  }
}
signed main() {
  init();
  solve();
  return 0;
}
