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

"Хорошие" перестановки

"Хорошие" перестановки

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

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

Например, перестановка 1 2 3 плохая, т.к. модули разностей будут 11, а вот перестановка 312 - хорошая, т.к. разности 2 1 образуют перестановку.

В этой задаче вам дано число n, и от вас требуется найти количество хороших перестановок из n чисел.

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

Выходные данные Вывести количество хороших перестановок чисел от 1 до n.

Пример

Входные данные #1
3
Выходные данные #1
4