Balanced Counting Rods

In ancient Chinese calculation, red rods are considered positive and black rods negative. Given a \(1 \times 2n\) matrix, you are free to place red and black rods such that the matrix remains balanced, i.e., for every prefix (from cell \(1\) to cell \(i\) for \(1 \leq i \leq 2n\)), the number of red rods is greater than or equal to the number of black rods. Additionally, the total number of red rods is equal to the total number of black rods.

This problem asks you to determine the number of valid arrangements. It turns out that the answer is given by the nth Catalan number, which can be expressed in \(\text{Catalan}(n) = \frac{1}{n+1}\binom{2n}{n}\) form.

inputFormat

The input consists of a single integer \(n\) (\(1 \leq n \leq 20\)), which represents half the length of the matrix (i.e., there are \(2n\) cells in total).

outputFormat

Output a single integer representing the number of valid configurations (i.e., the nth Catalan number).

sample

1

1