Two Round Dances#11602

Two Round Dances

1 second

128 megabytes

Easy

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 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]$ [1, 3, 4, 2], [4, 2, 1, 3] and $[2, 1, 3, 4]$ [2, 1, 3, 4] are indistinguishable.

Input

One even integer $n (2 \leq n \leq 20)$ n~(2 \le n \le 20).

Output

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$ n = 4 the number of ways is $3$ :

one round dance — $[1, 2]$ , another — $[3, 4]$ ;
one round dance — $[2, 4]$ , another — $[3, 1]$ ;
one round dance — $[4, 1]$ , another — $[3, 2]$ .

Example 1

Loading

[1, 3, 4, 2], [4, 2, 1, 3]

[2, 1, 3, 4]

n (2 \leq n \leq 20)

n = 4