CF959F.Mahmoud and Ehab and yet another xor task

Ehab has an array a of n integers. He likes the bitwise-xor operation 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.

Ehab 有一个包含 $n$ 个整数的数组 $a$。他喜欢按位异或（XOR）运算，也喜欢捉弄 Mahmoud，于是他想出了一个问题。他给了 Mahmoud $q$ 个查询。在每个查询中，他给出两个整数 $l$ 和 $x$，要求 Mahmoud 找出数组前 $l$ 个元素的所有子序列中，其按位异或和等于 $x$ 的子序列个数。你能帮 Mahmoud 回答这些查询吗？

子序列中的元素不必相邻。

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.

第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 10^5$），分别表示数组的元素个数和查询次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \leq a_i < 2^{20}$），表示数组的元素。

接下来 $q$ 行，每行包含两个整数 $l$ 和 $x$（$1 \leq l \leq n$，$0 \leq x < 2^{20}$），表示一次查询。

For each query, output its answer modulo 109 + 7 in a newline.

对于每个查询，请在新的一行中输出其答案对 $10^9 + 7$ 取模的结果。

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.

空集的按位异或和为 0，仅包含一个元素的集合的按位异或和即为该元素本身。