A hoard contains n relics, each engraved with a non-negative integer. A bundle is any subset of the relics (the empty bundle is allowed and its XOR is defined as 0). Count how many distinct bundles have a combined XOR (the XOR of all chosen engravings) exactly equal to a target value t.
Two bundles are considered different if they use a different set of relic positions, even when two relics share the same engraving.
Input format
Line 1: two space-separated integers n and t.
Line 2: n space-separated non-negative integers, the engravings.
Output format
A single integer: the number of bundles whose XOR equals t.
Constraints
- 1 <= n <= 20
- 0 <= t <= 1000000000
- 0 <= each engraving <= 1000000000