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

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

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

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

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

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