eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Красивый ряд

Красивый ряд

Лимит времени 2 секунды
Лимит использования памяти 244 MiB

Али-Амир выписал n чисел в ряд. Ряд чисел считается красивым, если любые два соседних числа имеют одинаковое количество единиц в двоичной или в троичной системе счисления.

Али-Амир задумался, сколькими способами все имеющиеся числа можно выписать в красивый ряд.

Входные данные

В первой строке находится число n (2n20). В следующей строке записаны n целых неотрицательных чисел, каждое из которых не превосходит 10^9.

Выходные данные

Выведите количество способов расположить все n чисел в красивый ряд.

Пример

Входные данные #1
3
5 1 6
Выходные данные #1
2
Источник 2012 VIII Жаутыковская олимпиада Алматы, Казахстан, 17 января