E. Два хоровода
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Однажды $$$n$$$ человек ($$$n$$$ — чётное число) собрались на площади и организовали два хоровода, в каждом из которых танцевало по $$$\frac{n}{2}$$$ человек ровно. Ваша задача — найти, сколькими способами $$$n$$$ человек могут составить два хоровода размера $$$\frac{n}{2}$$$. Каждый из человек должен танцевать ровно в одном из двух хороводов.

Хоровод — это танцевальный круг, который составляют $$$1$$$ или более человек. Два хоровода неотличимы, если один можно перевести в другой выбором начального участника хоровода. Например, хороводы $$$[1, 3, 4, 2]$$$, $$$[4, 2, 1, 3]$$$ и $$$[2, 1, 3, 4]$$$ — неотличимы.

Например, если $$$n=2$$$, то искомое количество способов равно $$$1$$$: один хоровод будет составлен первым человеком, а второй — вторым.

Например, если $$$n=4$$$, то искомое количество способов равно $$$3$$$. Возможные варианты:

  • один хоровод — $$$[1,2]$$$, другой — $$$[3,4]$$$;
  • один хоровод — $$$[2,4]$$$, другой — $$$[3,1]$$$;
  • один хоровод — $$$[4,1]$$$, другой — $$$[3,2]$$$.

Итак, ваша задача — найти, сколькими способами $$$n$$$ человек могут составить два хоровода размера $$$\frac{n}{2}$$$.

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

Входные данные состоят из единственного целого числа $$$n$$$ ($$$2 \le n \le 20$$$), $$$n$$$ — чётное число.

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

Выведите единственное целое число — количество способов организовать хороводы. Гарантируется, что ответ помещается в $$$64$$$-битный целочисленный тип данных.

Примеры
Входные данные
2
Выходные данные
1
Входные данные
4
Выходные данные
3
Входные данные
8
Выходные данные
1260
Входные данные
20
Выходные данные
12164510040883200