Problems
Two Round Dances
Two Round Dances
One day $n$ people ($n$ is even) met on a plaza and made two round dances. Find the number of ways $n$ people can make two round dances if each round dance consists of exactly $n / 2$ people. Each person should belong to exactly one of these two round dances.
Round dance is a dance circle consisting of $1$ or more people. Two round dances are \textbf{indistinguishable (equal)} if one can be transformed to another by choosing the first participant. For example, round dances $[1, 3, 4, 2], [4, 2, 1, 3]$ and $[2, 1, 3, 4]$ are indistinguishable.
\InputFile
One even integer $n~(2 \le n \le 20)$.
\OutputFile
Print the number of ways to make two round dances. It is guaranteed that the answer fits in the $64$-bit integer data type.
\Examples
For example, for $n = 4$ the number of ways is $3$:
\begin{itemize}
\item one round dance --- $[1, 2]$, another --- $[3, 4]$;
\item one round dance --- $[2, 4]$, another --- $[3, 1]$;
\item one round dance --- $[4, 1]$, another --- $[3, 2]$.
\end{itemize}
Input example #1
4
Output example #1
3