← 返回题目列表

Codeforces · 2066/C

C. 按位幻灯片

中文机器翻译题面 查看原题

给你一个数组 $$$a_1, a_2, \ldots, a_n$$$。此外,还给您三个变量 $$$P,Q,R$$$,最初等于 0。

您需要按照从$$$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$$$ 必须不是两两不同。

总共有 $$$3^n$$$ 种方法来执行所有 $$$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$$$。

输出

对于每个测试用例,输出在不违反主要规则的情况下执行所有 $$$n$$$ 操作的方法数量,以 $$$10^9 + 7$$$ 为模。

示例

输入 #1

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

输出 #1

3
9
39
123
3

注意

在第一个测试用例中,有 3 个有效的操作序列:PPP、QQQ、RRR。

在第二个测试用例中,有 9 个有效的操作序列:PPPP、PPPQ、PPPR、QQQP、QQQQ、QQQR、RRRP、RRRQ、RRRR。