e-olymp
Competitions

Azerbaijan Programming Olympiad - 2nd Stage preparation

Hands Shaking

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 (2n50).

Output

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

Time limit 1 second
Memory limit 64 MiB
Input example
2
4
8
Output example
1
2
14