Handshake

Consider a meeting of $n$ businessmen sitting around a circular table. To start the meeting, they must shake hands. Each businessman shakes the hand of exactly one other businessman. All handshakes happen simultaneously. We say that the shake is perfect if no arms cross each other.

Find the number of perfect shakes that exist for $n$ businessmen.

Input

Each line contains one even integer $n(2\le n\le 50)$.

Output

For each value of $n$ print in a separate line the number of perfect shakes that exist for $n$ businessmen.

Examples