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 $10^9 + 7$.

Input format

• The first line of input contains an integer $T$ denoting the number of test cases.
• The first line of each test case contains an integer $N$.
• The second line of each test case contains $N$ space-separated integers $A_1, A_2, \cdots, A_N$.

Output format

For each test case, print the answer in a separate line.

Constraints

$1 \leq T \leq 10 \\ 1 \leq N \leq 10^5 \\ 0 \leq A_i \leq 10^9$