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 _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ < 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.
[samples]
## 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.
Ehab 有一个包含 $n$ 个整数的数组 $a$。他喜欢按位异或运算，并且喜欢打扰 Mahmoud，因此他想出了一个问题。他给了 Mahmoud $q$ 个查询。在每个查询中，他给 Mahmoud 两个整数 $l$ 和 $x$，并要求他找出数组前 $l$ 个元素的子序列中，其按位异或和等于 $x$ 的子序列数量。你能帮助 Mahmoud 回答这些查询吗？
子序列可以包含不相邻的元素。
第一行包含整数 $n$ 和 $q$ $ (1 ≤ n, q ≤ 10^5) $，分别是数组中元素的数量和查询的数量。
下一行包含 $n$ 个整数 $a_1$, $a_2$, $\dots$, $a_n$ $ (0 ≤ a_i < 2^{20}) $，表示数组的元素。
接下来的 $q$ 行，每行包含两个整数 $l$ 和 $x$ $ (1 ≤ l ≤ n, 0 ≤ x < 2^{20}) $，表示一个查询。
对于每个查询，请在一行中输出其答案对 $10^9 + 7$ 取模的结果。
空集的按位异或和为 0，仅包含一个元素的集合的按位异或和即为该元素本身。
## Input
第一行包含整数 $n$ 和 $q$ $ (1 ≤ n, q ≤ 10^5) $，分别是数组中元素的数量和查询的数量。下一行包含 $n$ 个整数 $a_1$, $a_2$, $\dots$, $a_n$ $ (0 ≤ a_i < 2^{20}) $，表示数组的元素。接下来的 $q$ 行，每行包含两个整数 $l$ 和 $x$ $ (1 ≤ l ≤ n, 0 ≤ x < 2^{20}) $，表示一个查询。
## Output
对于每个查询，请在一行中输出其答案对 $10^9 + 7$ 取模的结果。
[samples]
## Note
空集的按位异或和为 0，仅包含一个元素的集合的按位异或和即为该元素本身。
**Definitions**
Let $ n, q \in \mathbb{Z}^+ $ denote the length of the array and the number of queries.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers with $ a_i \in \{0, 1, \dots, 2^{20} - 1\} $.
For each query $ j \in \{1, \dots, q\} $, let $ l_j \in \{1, \dots, n\} $ and $ x_j \in \{0, 1, \dots, 2^{20} - 1\} $ be given.
**Constraints**
1. $ 1 \leq n, q \leq 10^5 $
2. $ 0 \leq a_i < 2^{20} $ for all $ i \in \{1, \dots, n\} $
3. $ 1 \leq l_j \leq n $, $ 0 \leq x_j < 2^{20} $ for all $ j \in \{1, \dots, q\} $
**Objective**
For each query $ j $, compute the number of subsequences of the prefix $ A_{l_j} = (a_1, a_2, \dots, a_{l_j}) $ whose bitwise XOR sum equals $ x_j $.
Let $ S \subseteq \{1, 2, \dots, l_j\} $ be a subset of indices. Define the XOR sum of the subsequence indexed by $ S $ as:
$$
\bigoplus_{i \in S} a_i
$$
where $ \bigoplus $ denotes bitwise XOR, and the XOR over the empty set is 0.
Let $ f_j = \left| \left\{ S \subseteq \{1, \dots, l_j\} \ \middle|\ \bigoplus_{i \in S} a_i = x_j \right\} \right| $.
Output $ f_j \mod (10^9 + 7) $ for each query $ j $.