Valid Parentheses Combinations

You are given an integer (n) representing the number of pairs of parentheses. Your task is to compute the number of distinct valid parentheses combinations that can be formed using exactly (n) pairs. A combination is valid if and only if every opening parenthesis has a corresponding closing parenthesis, and at no point does the number of closing parentheses exceed the number of opening ones. The answer is given by the (n)-th Catalan number, where the formula is given in (\LaTeX) as:

[ C_n = \frac{1}{n+1} \binom{2n}{n} ]

A valid parentheses string of length (2n) is one that adheres to these conditions. Your program should read the input from standard input and output the result to standard output.

inputFormat

The input consists of a single integer (n) (where (1 \le n \le 20)), which represents the number of pairs of parentheses. The number is provided via standard input.

outputFormat

Output a single integer, which is the number of valid parentheses combinations of length (2n), printed to standard output.## sample

1

1