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 = 1e5 + 5;
bool cmax(int &a, int b) { return (a < b) ? a = b, 1 : 0; }
bool cmin(int &a, int b) { return (a > b) ? a = b, 1 : 0; }
template <typename T>
T read() {
  T ans = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch) && ch != '-') ch = getchar();
  if (ch == '-') f = -1, ch = getchar();
  while (isdigit(ch))
    ans = (ans << 3) + (ans << 1) + (ch - '0'), ch = getchar();
  return ans * f;
}
template <typename T>
void write(T x, char y) {
  if (x == 0) {
    putchar('0');
    putchar(y);
    return;
  }
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  static char wr[20];
  int top = 0;
  for (; x; x /= 10) wr[++top] = x % 10 + '0';
  while (top) putchar(wr[top--]);
  putchar(y);
}
void file() {}
int n, m;
int a[N], ans[N];
vector<pair<int, int> > q[N];
void input() {
  int l, x;
  n = read<int>();
  m = read<int>();
  for (register int i = (int)1; i <= (int)n; ++i) a[i] = read<int>();
  for (register int i = (int)1; i <= (int)m; ++i) {
    l = read<int>(), x = read<int>();
    q[l].push_back(pair<int, int>(x, i));
  }
}
int cnt, p[21];
void insert(int x) {
  for (register int i = (int)20; i >= (int)0; --i) {
    if (x >> i) {
      if (!p[i]) {
        p[i] = x;
        ++cnt;
        return;
      }
      x ^= p[i];
    }
  }
}
bool check(int x) {
  for (register int i = (int)20; i >= (int)0; --i) {
    if (x >> i) {
      if (!p[i]) return false;
      x ^= p[i];
      if (!x) return true;
    }
  }
  return x ? false : true;
}
int pw2[N];
void work() {
  pair<int, int> t;
  for (register int i = (int)1; i <= (int)n; ++i) {
    insert(a[i]);
    for (register int j = (int)0; j <= (int)q[i].size() - 1; ++j) {
      t = q[i][j];
      if (check(t.first)) ans[t.second] = pw2[i - cnt];
    }
  }
  for (register int i = (int)1; i <= (int)m; ++i) write(ans[i], '\n');
}
const int mo = 1e9 + 7;
void init() {
  pw2[0] = 1;
  for (register int i = (int)1; i <= (int)n; ++i)
    pw2[i] = (pw2[i - 1] << 1) % mo;
}
int main() {
  file();
  input();
  init();
  work();
  return 0;
}
