C. Bitwise Slidestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output 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$$$.InputEach 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$$$.OutputFor each test case, output the number of ways to perform all $$$n$$$ actions without violating the main rule, modulo $$$10^9 + 7$$$.ExampleInput531 7 94179 1 1 17951 2 3 3 2128 2 5 3 9 1 8 12 9 9 9 411000000000Output3 9 39 123 3 NoteIn 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.