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] and [2,1,3,4] are indistinguishable.
One even integer n (2≤n≤20).
Print the number of ways to make two round dances. It is guaranteed that the answer fits in the 64-bit integer data type.
For example, for 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].