Однажды $$$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}$$$.