Migrated from Lutece 2057 简单异或

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给出一个长度为n的数列A和m次询问,每次询问包含两个整数r,x 询问的结果是 数列A的前 r 个元素中取任意个元素 有多少种方案使得 选取的元素的异或和为 x（一个元素也不取的时候，异或和为0）。

Input

第一行两个整数， 分别为n和m，( 1<=n,m<=100000 )分别代表数列的长度和询问的数量； 第二行有n个整数，第i个数代表Ai，即数列A的第i个元素值( 0<=Ai<=1000000 )； 接下来有m行，每行两个数字 r , x ，( 1<= r <= n , 0<= x <= 1000000 ) 代表每次询问的参数。

Output

对于每次询问输出 询问的答案对 1e9+7 的余数

Samples

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

2
2
2
0
4

Note

第一个询问：数列的前1个元素选取任意个 ，其异或和为 0 的方案数为2 ,满足条件的两个方案的元素集合分别为 空集 和 { 0 }
第二个询问：数列的前2个元素选取任意个 ，其异或和为 0 的方案数为2 ,满足条件的两个方案的元素集合分别为 空集 和 { 0 }
第三个询问：数列的前3个元素选取任意个 ，其异或和为 3 的方案数为2 ,满足条件的两个方案的元素集合分别为 { 1 , 2} 和 { 0 , 1 , 2 }
第四个询问：数列的前4个元素选取任意个 ，其异或和为 7 的方案数为0 ,不存在满足要求的方案
第五个询问：数列的前5个元素选取任意个 ，其异或和为 7 的方案数为4 ,满足条件的四个方案的元素集合分别为 { 0 , 1 , 2 ,4 } 和 { 0 , 3 4 } 和 { 1 , 2 , 4 } 和 { 3 , 4 }

Resources

每周一题 div 1