Вам задано n целых чисел a1, a2, ..., an.
Последовательность целых чисел x1, x2, ..., xk называется "xor-последовательностью", если для всех 1 ≤ i ≤ k - 1 количество единиц в двоичном представлении числа xi 
xi + 1 кратно трём и 
для всех 1 ≤ i ≤ k. Знак обозначает операцию двоичного исключающего или.
Найдите количество "xor-последовательностей" длины k по модулю 109 + 7.
Обратите внимание, если a = [1, 1] и k = 1, то ответ равен 2, поскольку вы должны рассматривать единицы из a как разные.
Выходные данные
Выведите единственное число c — количество "xor-последовательностей" длины k по модулю 109 + 7.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
15 1 2 4 8
|
13
|
|
2
|
5 1
15 1 2 4 8
|
5
|