You are given an array of n non-negative integers and a target value k. Consider every one of the 2^n subsets of the array (the empty subset is included and its XOR is defined as 0). Count how many subsets have a bitwise XOR of their elements exactly equal to k.
The answer is a single well-defined count, so it is unique. Note that the count can be as large as 2^n, so use a 64-bit-capable integer type.
A key fact: over GF(2), if the array's values span a linear space of rank r, then either no subset reaches k (answer 0), or exactly 2^(n - r) subsets do. You are encouraged to build a linear basis rather than enumerate all subsets, though for the given constraints enumeration would also fit in time.
Input format
Line 1: two space-separated integers n and k.
Line 2: n space-separated non-negative integers (this line is present but blank when n = 0).
Output format
A single integer: the number of subsets whose XOR equals k.
Constraints
- 0 ≤ n ≤ 40
- 0 ≤ k ≤ 1000000000
- 0 ≤ each array value ≤ 1000000000