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>
clock_t t = clock();
namespace my_std {
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
inline T rnd(T l, T r) {
  return uniform_int_distribution<T>(l, r)(rng);
}
template <typename T>
inline bool chkmax(T& x, T y) {
  return x < y ? x = y, 1 : 0;
}
template <typename T>
inline bool chkmin(T& x, T y) {
  return x > y ? x = y, 1 : 0;
}
template <typename T>
inline void read(T& t) {
  t = 0;
  char f = 0, ch = getchar();
  double d = 0.1;
  while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
  while (ch <= '9' && ch >= '0') t = t * 10 + ch - 48, ch = getchar();
  if (ch == '.') {
    ch = getchar();
    while (ch <= '9' && ch >= '0') t += d * (ch ^ 48), d *= 0.1, ch = getchar();
  }
  t = (f ? -t : t);
}
template <typename T, typename... Args>
inline void read(T& t, Args&... args) {
  read(t);
  read(args...);
}
char sr[1 << 21], z[20];
int C = -1, Z = 0;
inline void Ot() { fwrite(sr, 1, C + 1, stdout), C = -1; }
inline void print(register int x) {
  if (C > 1 << 20) Ot();
  if (x < 0) sr[++C] = '-', x = -x;
  while (z[++Z] = x % 10 + 48, x /= 10)
    ;
  while (sr[++C] = z[Z], --Z)
    ;
  sr[++C] = '\n';
}
void file() {}
inline void chktime() {}
long long ksm(long long x, int y) {
  long long ret = 1;
  for (; y; y >>= 1, x = x * x % 1000000007)
    if (y & 1) ret = ret * x % 1000000007;
  return ret;
}
long long inv(long long x) { return ksm(x, 1000000007 - 2); }
}  // namespace my_std
using namespace my_std;
struct hh {
  int a[25], size;
  void insert(long long x) {
    for (int i = (21); i >= (0); i--)
      if (x & (1 << i)) {
        if (!a[i]) return (void)(a[i] = x, ++size);
        x ^= a[i];
      }
  }
  bool in(int x) {
    for (int i = (21); i >= (0); i--)
      if (x & (1 << i)) {
        if (!a[i]) return 0;
        x ^= a[i];
      }
    return 1;
  }
} a[101010];
int n, m;
int main() {
  file();
  int x, y;
  read(n, m);
  for (int i = (1); i <= (n); i++) {
    a[i] = a[i - 1];
    scanf("%d", &x);
    a[i].insert(x);
  }
  while (m--) {
    scanf("%d %d", &x, &y);
    if (a[x].in(y))
      printf("%lld\n", ksm(2, x - a[x].size));
    else
      puts("0");
  }
  return 0;
}
