Красивий рядок

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

Алі-Амір зацікавився, скількома способами можна розташувати всі наявні числа в красивий рядок.

Вхідні дані

У першому рядку задано число n (2 ≤ n ≤ 20). У наступному рядку наведено n цілих невід'ємних чисел, кожне з яких не перевищує 10^9.

Вихідні дані

Виведіть кількість способів розташувати всі n чисел у красивий рядок.

Приклади