Задача D. Красивый ряд ≡

Автор:	Жаутыковская олимпиада 2012		Ограничение времени:	3 сек
Входной файл:	input.txt		Ограничение памяти:	256 Мб
Выходной файл:	output.txt
Максимальный балл:	100

Условие

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

Формат входного файла

В первой строке входного файла находится число N. В следующей строке записаны N чисел a[i].

Формат выходного файла

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

Ограничения

2 ≤ N ≤ 20, 0 ≤ a[i] ≤ 10⁹

Примеры тестов

№	Входной файл (input.txt)	Выходной файл (output.txt)
1	3 5 1 6 скопировать	2 скопировать

---