Вам дан массив \(a_1, a_2, \ldots, a_n\). А также три переменные \(P,Q,R\), изначально равные нулю.
Вам необходимо поочерёдно обработать все числа \(a_1, a_2, \ldots, a_n\), в порядке от \(1\) до \(n\). Обрабатывая очередное \(a_i\), вы должны сделать ровно одно из трёх действий на выбор:
- \(P := P \oplus a_i\)
- \(Q := Q \oplus a_i\)
- \(R := R \oplus a_i\)
\(\oplus\) обозначает операцию побитового исключающего ИЛИ.
Выполняя действия, надо соблюдать главное правило: необходимо, чтобы после каждого действия все три числа \(P,Q,R\) не были попарно различны.
Всего есть \(3^n\) способов произвести все \(n\) действий. Сколько из них не нарушают главное правило? Так как ответ может быть достаточно большим, найдите его по модулю \(10^9 + 7\).
Выходные данные
Для каждого набора входных данных выведите количество способов произвести все \(n\) действий, не нарушая главное правило, по модулю \(10^9 + 7\).
Примечание
В первом наборе входных данных 3 валидные последовательности операций: PPP, QQQ, RRR
Во втором наборе входных данных 9 валидных последовательностей операций: PPPP, PPPQ, PPPR, QQQP, QQQQ, QQQR, RRRP, RRRQ, RRRR.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
3
9
39
123
3
|