Bitwise Slides
Contest: Codeforces Round 1004 (Div. 1)
Difficulty rating: 2300
Tags: 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:

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 format:
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 format:
For each test case, output the number of ways to perform all $$$n$$$ actions without violating the main rule, modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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.

Example input:
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

Example output:
3
9
39
123
3

Editorial:
Let us denote $$$pref_i = a_1 \oplus \ldots \oplus a_i$$$ — the array of prefix $$$XOR$$$s.
Notice that after the $$$i$$$-th action, it is always true that $$$P \oplus Q \oplus R = pref_i$$$, regardless of which actions were chosen.
With this knowledge, we can say that after the $$$i$$$-th action, the condition "the numbers $$$P, Q, R$$$ are not pairwise distinct" is equivalent to the condition "at least one of $$$P, Q, R$$$ equals $$$pref_i$$$." This is because if there is a pair of equal numbers among $$$P, Q, R$$$, their $$$XOR$$$ equals $$$0$$$, which means the third number must equal $$$pref_i$$$.
Thus, all possible valid states $$$(P, Q, R)$$$ after the $$$i$$$-th action look like: $$$(pref_i, x, x), (x, pref_i, x), (x, x, pref_i)$$$ for some $$$x$$$.
After this observation, we can try to write a dynamic programming solution: $$$dp[i][x]$$$ — the number of ways to reach one of the states of the form $$$(pref_i, x, x), (x, pref_i, x), (x, x, pref_i)$$$ after the $$$i$$$-th action.
At first glance, this dynamic programming approach seems to take an unreasonable amount of time and memory. However, we will still outline its base case and recurrence.
Base case: $$$dp[0][0] = 1$$$.
Recurrence: suppose we want to recalculate $$$dp[i][x]$$$ using $$$dp[i-1][*]$$$. From which state can we arrive at $$$(x, x, pref_i)$$$ if the last move involved XORing one of the variables with $$$a_i$$$? There are three possible cases: $$$(x \oplus a_i, x, pref_i)$$$, $$$(x, x \oplus a_i, pref_i)$$$, $$$(x, x, pref_i \oplus a_i)$$$.
The number of ways to reach the state $$$(x, x, pref_i \oplus a_i)$$$ is actually equal to $$$dp[i-1][x]$$$, since $$$pref_i \oplus a_i = pref_{i-1}$$$.
What about the case $$$(x \oplus a_i, x, pref_i)$$$? For the state to be valid from the previous move, two of these numbers must be equal, and the third must equal $$$pref_{i-1}$$$.
However, we know that $$$pref_i \neq pref_{i-1}$$$, since $$$a_i \neq 0$$$. Therefore, either $$$x \oplus a_i = pref_{i-1}$$$ (which means $$$x = pref_i$$$), or $$$x = pref_{i-1}$$$.
If $$$x = pref_i$$$, then the value of $$$dp[i][x]$$$ is also equal to $$$dp[i-1][x]$$$, because the state $$$(pref_i, pref_i, pref_i)$$$ can be reached from one of the states $$$(pref_{i-1}, pref_i, pref_i)$$$, $$$(pref_i, pref_{i-1}, pref_i)$$$, $$$(pref_i, pref_i, pref_{i-1})$$$, and the number of ways to reach one of these states after the $$$(i-1)$$$-th move is literally defined as $$$dp[i-1][pref_i]$$$.
For $$$x = pref_{i-1}$$$: $$$dp[i][pref_{i-1}] = 3 \cdot dp[i-1][pref_{i-1}] + 2 \cdot dp[i-1][pref_i]$$$. There are a total of 3 ways to arrive from $$$(pref_{i-1}, pref_{i-1}, pref_{i-1})$$$, and 2 ways from the states $$$(pref_{i-1}, pref_i, pref_i)$$$, $$$(pref_i, pref_{i-1}, pref_i)$$$, $$$(pref_i, pref_i, pref_{i-1})$$$.
In summary, the only $$$x$$$ for which $$$dp[i][x] \neq dp[i-1][x]$$$ is $$$x = pref_{i-1}$$$.
Therefore, unexpectedly, we do not need to recalculate the entire array $$$dp$$$, but only one of its values. And of course, since the elements of the array are quite large, we will store this $$$dp$$$ in a regular map.
The answer to the problem will be the sum of all values of $$$dp$$$ at the end of the process.