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:

$$$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

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$$$.

Note

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.

Bitwise Slides

Examples