B. Pair Partitioning
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Determine in how many ways the natural numbers from $$$1$$$ to $$$2n$$$ can be partitioned into $$$n$$$ pairs so that in each pair, the second number was at least twice the first

Input

The only line of the input contains an integer $$$n$$$ ($$$1 \le n \le 25$$$).

Output

Print one integer — the answer.

Example
Input
3
Output
2
Note

In the example, two valid sets of pairs can be formed: 1 – 5, 2 – 4, 3 – 6 and 1 – 4, 2 – 5, 3 – 6.