在数字理论中,异或运算是一种常见且重要的运算方式。小途是一位探索者,他研究了异或运算在整数数组中的应用。现在,他面临一个新的问题,需要计算满足条件的子数组量。
给定一个长度为n的非负整数数组,你需要计算有多少个子数组的异或和等于给定的非负整数k,答案对 10^9+7 + 取模。
输入的第一行包含两个整数,分别为数组的长度n和目标异或和k。
输入的第二行包含n个非负整数 a_i ,表示数组中的元素。
输出一个整数,表示满足条件的子数组的数量。
5 2 1 2 3 4 5
2
样例解释
有两个子数组的异或和等于2, 分别是[2] 和 [3,4,5]。
对于20%的数据, n=3 ;
对于另外20%的数据, n≤100 ;
对于另外20%的数据, n≤100000, a_i=k ;
对于另外20%的数据, n≤50000, k=0 ;
对于100%的数据, 1≤n≤100000,0≤a_i,k≤2^{31}―1 。