You are given an array $a_1, a_2, \ldots, 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, \ldots, 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:

1. $P := P \oplus a_i$
2. $Q := Q \oplus a_i$
3. $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

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

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

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 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 \cdot 10^5$.

Output

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

见题面 Input 部分

见题面 Output 部分

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.