C. Bitwise Slides

题目描述

给定一个数组 $a_1,a_2,\dots,a_n$。同时给定三个变量 $P,Q,R$，初始值均为 $0$。

你需要按照从 $1$ 到 $n$ 的顺序处理数组中的所有数字。处理下一个数字 $a_i$ 时，你必须恰好选择执行以下三种操作之一：

• $P := P \oplus a_i$
• $Q := Q \oplus a_i$
• $R := R \oplus a_i$

其中 $\oplus$ 表示**按位异或（XOR）**运算。

执行操作时必须遵守核心规则：在每一次操作结束后，三个数 $P,Q,R$ 不能两两互不相同。

总共有 $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,\dots,a_n$（$1 \le a_i \le 10^9$）。

保证所有测试数据的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每组测试数据，输出一个整数，表示合法的操作方案数对 $10^9+7$ 取模后的结果。

样例输入

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

样例输出

3
9
39
123
3

样例说明

• 在第一组测试用例中，合法的操作序列有 $3$ 种：$PPP, QQQ, RRR$。
• 在第二组测试用例中，合法的操作序列有 $9$ 种：$PPPP, PPPQ, PPPR, QQQP, QQQQ, QQQR, RRRP, RRRQ, RRRR$。