Catalan Numbers and Valid Parentheses

Given an integer n, count the number of distinct well-formed parentheses expressions that can be constructed using exactly n pairs of parentheses.

This number is given by the Catalan number:

$$ C_n = \frac{1}{n+1}\binom{2n}{n} $$

For example, when n = 3, there are 5 valid expressions.

inputFormat

The first and only line of input contains a single integer n (1 ≤ n ≤ 20), representing the number of pairs of parentheses.

outputFormat

Output a single integer, the number of distinct valid parentheses expressions that can be formed using exactly n pairs.

## sample

1

1

</p>