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\)