You are given an array A of N integers. A partitioning of the array A is the splitting of A into one or more non-empty contiguous subarrays such that each element of A belongs to exactly one of these subarrays.
Find the number of ways to partition A such that the Bitwise XOR of elements within each subarray has an odd number of set bits (i.e., 1s). Since the answer may be large, output the answer modulo 109+7.
Input format
Output format
For each test case, print the answer in a separate line.
Constraints
1≤T≤101≤N≤1050≤Ai≤109
For test case 1 - The array can be partitioned as follows
For test case 2 - The array can be partitioned as follows