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$$$.
A single integer $$$n$$$ is input ($$$1 \le n \le 50$$$).
Output a single integer — the number of symmetric CBS of length $$$2n$$$.
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$$$
3
3
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.
