C. Bitwise Slides
bitmasks; combinatorics; dp; math
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\).
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\).
For each test case, output the number of ways to perform all \(n\) actions without violating the main rule, modulo \(10^9 + 7\).
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.