C. Brackets
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A correct bracket sequence (CBS) is a string consisting only of round brackets, where each closing bracket has a corresponding opening one, and vice versa.

Examples of CBS: '()', '(())', '()(())'. Examples of strings that are not CBS: '())', ')(', '(()'.

A more strict definition of CBS:

  • an empty string is a CBS,
  • if the string $$$S$$$ is a CBS then the string $$$(S)$$$ is also a CBS,
  • if the strings $$$S$$$ and $$$R$$$ are CBS, then the string $$$SR$$$ is also a CBS.

Write a program to count the number of such CBS of length $$$2n$$$ that will remain CBS if you remove two central brackets (i.e., the brackets with numbers $$$n$$$ and $$$n+1$$$). For example, when $$$n$$$=3, the answer is 3 — these are the strings '((()))', '()()()', and '(()())'.

Input

Input one integer $$$n$$$ ($$$1 \le n \le 30$$$).

Output

Output one integer — the number of searched CBS.

Example
Input
3
Output
3