5. Symmetric Sequences
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A correct bracket sequence (CBS) is defined as a string consisting only of round brackets, where each closing bracket has a corresponding opening bracket, and vice versa. Examples of CBS: '()', '(())', '()(())'. Examples of strings that are not CBS: '())', ')(', '(()'.

We call a CBS of length $$$2n$$$ symmetric if for any $$$i$$$ from $$$1$$$ to $$$n$$$, it is true that the $$$i$$$-th bracket from the beginning is not equal to the $$$i$$$-th bracket from the end. For example, for $$$n=3$$$ the following CBS are symmetric: '((()))', '()()()', and '(()())'.

Write a program that calculates the number of symmetric CBS of length $$$2n$$$.

Input

A single integer $$$n$$$ is input ($$$1 \le n \le 50$$$).

Output

Output a single integer — the number of symmetric CBS of length $$$2n$$$.

Scoring

Subtask 1 (up to 45 points): $$$n \le 10$$$

Subtask 2 (up to 25 points): $$$n \le 20$$$

Subtask 3 (up to 30 points): $$$n \le 50$$$

Example
Input
3
Output
3
Note

Note that the answer in the last subtask can be quite large and may not fit into a 32-bit data type. It is recommended to use a 64-bit data type, for example, the long long type in C++, the int64 type in Pascal, the long type in Java and C#. Python automatically works with integers of any length.