C. Битовые горки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a_1, a_2, \ldots, a_n$$$. А также три переменные $$$P,Q,R$$$, изначально равные нулю.

Вам необходимо поочерёдно обработать все числа $$$a_1, a_2, \ldots, a_n$$$, в порядке от $$$1$$$ до $$$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$$$.

Пример
Входные данные
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.