Problem Description

Given \( N \) positive integers, the \( i \)-th (\( 1 \leq i \leq N \)) positive integer is \( a_i \).
Select zero or more integers from the \( N \) integers and calculate the bitwise XOR of all the selected integers.
Find the number of ways to select integers such that the result of the calculation is \( K \), modulo \( 10^9+7 \).
Note that the bitwise XOR of zero selected integers is considered to be \( 0 \).

Input Format

The input is given from the standard input in the following format:

\( N \) \( K \) \( a_1 \) \( : \) \( a_N \)

Output Format

Output the number of ways to select integers that satisfy the condition, modulo \( 10^9+7 \).

Sample Input and Output

Sample Input #1

4 3
1
2
1
2

Sample Output #1

4

Sample Input #2

4 0
1
1
1
1

Sample Output #2

8

Sample Input #3

13 3
2
7
1
8
2
8
1
8
2
8
4
5
9

Sample Output #3

512

Notes/Hints

Constraints

• \( 1 \leq N \leq 10^5 \)
• \( 0 \leq K \leq 10^5 \)
• \( 1 \leq a_i \) (\( 1 \leq i \leq N \))
• \( a_1 + \ldots + a_N \leq 10^5 \)
• All inputs are integers.

Sample Explanation 1

The ways to select integers such that the bitwise XOR of all selected integers is \( K = 3 \) are as follows:
- \( \{a_1, a_2\} \)
- \( \{a_1, a_4\} \)
- \( \{a_2, a_3\} \)
- \( \{a_3, a_4\} \)

Sample Explanation 2

The ways to select integers such that the bitwise XOR of all selected integers is \( K = 0 \) are as follows:
- \( \{\} \) (when zero integers are selected)
- \( \{a_1, a_2\} \)
- \( \{a_1, a_3\} \)
- \( \{a_1, a_4\} \)
- \( \{a_2, a_3\} \)
- \( \{a_2, a_4\} \)
- \( \{a_3, a_4\} \)
- \( \{a_1, a_2, a_3, a_4\} \)

见题面 Input 部分

见题面 Output 部分