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,而包含一个元素的集合的按位异或和是该元素本身。