E. Good Subsequences
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $$$A$$$ consisting of $$$N$$$ positive integers.

A sequence of integers is considered $$$\textbf{good}$$$ if the following condition holds:

  • Let $$$X$$$ be equal to the bitwise XOR of all elements in the sequence; then $$$X$$$ must have an odd number of on bits (bits that are equal to $$$1$$$) in its binary representation.

Your task is to count the number of different$$$^\ddagger$$$ non-empty good subsequences$$$^\dagger$$$ of $$$A$$$. Since the answer can be very large, print the answer modulo $$$10^9 + 7$$$.

$$$\dagger$$$  A sequence $$$B$$$ is a subsequence of $$$A$$$ if $$$B$$$ can be obtained from $$$A$$$ by deleting several (possibly none or all) elements (not necessarily adjacent).

$$$\ddagger$$$  Two subsequences are considered different if the sets of indexes of their elements in the original sequence are different; that is, the values of the elements are not considered when comparing the subsequences.

Input

The first line of input contains a single integer $$$T$$$ ($$$1 \le T \le 10^3$$$) — representing the number of testcases.

The first line of each testcase contains a single integer $$$N$$$ ($$$1 \le N \le 10^6$$$) — representing the number of elements in $$$A$$$.

The second line of each testcase contains $$$N$$$ space-separated integers ($$$1 \le a_i \lt 2^{30}$$$) — representing the elements of the array $$$A$$$.

It's guaranteed that the sum of $$$N$$$ over all test cases doesn't exceed $$$10^6$$$.

Output

For each test case, print a new line containing a single integer representing the number of good subsequences, modulo $$$10^9 + 7$$$.

Example
Input
6
1
2
1
3
2
2 3
2
1 4
3
1 2 7
3
10 3 2
Output
1
0
2
2
4
4