Pigtail Pairing

Interview

Time limit1sMemory limit1024 MB

Summary

Count the ways to split N labeled guests into pairs for two-person tables, where seat order and table order do not matter.

Level: Easy3 of 10
Topics: Math, Combinatorics, Recursion
Solved: No attempts yet

Problem

Siyeon's cafe is about to receive a group of pigtail customers. They love pigtails so much that they come in pairs, so the total number of guests is even.

The cafe has plenty of tables that seat two people each, and the guests agree to sit two to a table.

Given these rules, how many ways can all the pigtail guests be seated? Count arrangements under these conditions:

Seats at a table are not distinguished. Guest A sitting with guest B is the same as guest B sitting with guest A.
Tables are not distinguished either. Guests A and B at table 1 with C and D at table 2 is the same as C and D at table 1 with A and B at table 2.

Input

The first line contains the number of pigtail guests $N$ ( $2 \leq N \leq 28$ , $N$ is even).

Output

Print the number of ways the guests can be seated on the first line.

Intermediate results can exceed the range of a 32-bit integer, so watch out for overflow.

Examples2

Example 1
Input
```
2
```
Expected output
```
1
```
Example 2
Input
```
4
```
Expected output
```
3
```