"Гарні" перестановки

Будемо називати перестановку цілих чисел від 1 до n гарною тоді і лише тоді, коли модулі різниць між сусідніми числами утворюють перестановку від 1 до n - 1.

Наприклад, перестановка 1 2 3 не гарна, так як модулі різниць будуть 1 1, а ось перестановка 3 1 2 - гарна, так як різниці 2 1 утворюють перестановку.

У цій задачі вам задано число n, і вам потрібно знайти кількість гарних перестановок з n чисел.

Вхідні дані Одне ціле число n (2 ≤ n ≤ 30).

Вихідні дані Вивести кількість гарних перестановок чисел від 1 до n.

Приклади