There is a class of n students. Each student has a specific id A[i] for each valid i. A teacher divided a class of n students into equal groups.
Each group is assigned a task.
1st group: Find number of subsets of A such that their cumulative xor is less than K.
2nd group : Find number of subsets of A such that their cumulative xor is equal to K.
3rd group : Find number of subsets of A such that their cumulative xor is greater than K.
Let answer of first group be c1, second group be c2 and third group be c3.
Teacher does not tolerate direct answers, So he asked the group to represent answer in encoded format :
ANS : ( (c1 + c2)2 + (c2 + c3)2 + (c1 + c3)2 - (c12 + c22 + c32) ) % 1000000007
INPUT:
The first line contains t ( number of test cases ). (1<=t<=100).
For each test case:
First line contains 2 integers separated by space n ( 1<=n<=105 )
and K ( 1<=K<= 109 ).
Next line contains n integers. For all valid i ( 1<=A[i]<=109 )
OUTPUT:
For each test case:
Print one line containing ANS according to above conditions
