← 返回题目列表

Codeforces · 959/F

F. Mahmoud 和 Ehab 以及另一个异或任务

中文机器翻译题面 查看原题

Ehab 有一个包含 n 个整数的数组 a。他喜欢按位异或运算,并且喜欢打扰 Mahmoud,所以他提出了一个问题。他向马哈茂德提出了问题。在每一个中,他给了 Mahmoud 2 个整数 l 和 x,并要求他找到数组的前 l 个元素的子序列的数量,使得它们的按位异或和为 x。你能帮助马哈茂德回答问题吗?

子序列可以包含不相邻的元素。

输入

第一行包含整数 n 和 q (1 ≤ n, q ≤ 105)、数组中的元素数量和查询次数。

下一行包含 n 个整数 a1, a2, ..., an (0 ≤ ai < 220),即数组的元素。

接下来的 q 行,每行包含整数 l 和 x (1 ≤ l ≤ n, 0 ≤ x < 220),代表查询。

输出

对于每个查询,在换行符中输出其答案模 109 + 7。

示例

输入 #1

5 5
0 1 2 3 4
4 3
2 0
3 7
5 7
5 8

输出 #1

4
2
0
4
0

输入 #2

3 2
1 1 1
3 1
2 0

输出 #2

4
2

注意

空集的按位异或和为 0,而包含一个元素的集合的按位异或和是该元素本身。