1408. Count Arrays with XOR Equal to K (Linear Basis)

Given an array of non-negative integers and a target k, count the subsets (including the empty subset) whose XOR equals k. Return the count modulo 1000000007. The count depends only on whether k lies in the span of the values and on the rank of that span.

Input: A JSON object {"nums": [<non-negative integers>], "k": <target>}.

Output: Return the number of subsets with XOR equal to k, modulo 1000000007.

Examples

Input: {"nums":[1,2,3],"k":0}
Output: 2
Explanation: The empty subset and {1,2,3} both XOR to 0 -> 2.

Input: {"nums":[6,9,4,2],"k":6}
Output: 2
Explanation: Two subsets XOR to 6.

Constraints

• 1 <= len(nums) <= 10^5
• 0 <= nums[i], k < 2^30

Asked by