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

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

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

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

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

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

Примеры