CF2066C Bitwise Slides

给定一个数组 $a_1, a_2, \ldots, a_n$，以及三个初始值为零的变量 $P, Q, R$。 你需要按从 $1$ 到 $n$ 的顺序依次处理所有数字 $a_1, a_2, \ldots, a_n$。当处理当前元素 $a_i$ 时，你必须从以下三个操作中任选一个执行： 1. $P := P \oplus a_i$ 2. $Q := Q \oplus a_i$ 3. $R := R \oplus a_i$ 其中 $\oplus$ 表示按位异或操作。 执行操作时必须遵守核心规则：每次操作后，三个数 $P, Q, R$ 必须满足其中至少存在两个数相等。 所有 $n$ 个操作共有 $3^n$ 种可能的执行方式。求其中不违反核心规则的方式数量。由于答案可能很大，请输出其对 $10^9 + 7$ 取模的结果。

每个测试包含多个测试用例。第一行输入测试用例数 $t$（$1 \le t \le 10^4$）。随后为各测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——数组 $a$ 的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）——数组 $a$ 的元素。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出不违反核心规则的操作方式数量对 $10^9 + 7$ 取模后的结果。

第一个测试用例中，存在 3 种合法操作序列：PPP、QQQ、RRR。 第二个测试用例中，存在 9 种合法操作序列：PPPP、PPPQ、PPPR、QQQP、QQQQ、QQQR、RRRP、RRRQ、RRRR。 翻译由 DeepSeek R1 完成