Problem: codeforces/2067F
Time limit: 2000 ms, Memory limit: 256 MB

You are given an array a_1, a_2, ..., a_n. Also, you are given three variables P, Q, R, initially equal to zero.

You need to process all the numbers a_1, a_2, ..., a_n, in the order from 1 to n. When processing the next a_i, you must perform exactly one of the three actions of your choice:

P := P \oplus a_i
Q := Q \oplus a_i
R := R \oplus a_i

\oplus denotes the bitwise XOR operation.

When performing actions, you must follow the main rule: it is necessary that after each action, all three numbers P, Q, R are not pairwise distinct.

There are a total of 3^n ways to perform all n actions. How many of them do not violate the main rule? Since the answer can be quite large, find it modulo 10^9+7.


Input Format

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10^4). The description of the test cases follows.

The first line of each test case contains an integer n (1 ≤ n ≤ 2⋅10^5) — the length of the array a.

The second line of each test case contains n integers a_1, 𝑎_2, ..., a_n (1≤ a_i ≤ 10^9) — the elements of the array a.

It is guaranteed that the sum of the values of n for all test cases does not exceed 2⋅10^5.

Output Format

For each test case, output the number of ways to perform all n actions without violating the main rule, modulo 10^9+7.


Sample Input 1

```
5
3
1 7 9
4
179 1 1 179
5
1 2 3 3 2
12
8 2 5 3 9 1 8 12 9 9 9 4
1
1000000000
```

Sample Output 1

```
3
9
39
123
3
```

Notes

In the first test case, there are 3 valid sequences of operations: PPP, QQQ, RRR.

In the second test case, there are 9 valid sequences of operations: PPPP, PPPQ, PPPR, QQQP, QQQQ, QQQR, RRRP, RRRQ, RRRR.