Counting Stack Permutations

In this problem, you are given a sequence of operands 1, 2, ..., n and a stack A with sufficient depth. You can perform the following two operations:

1. Take a number from the front of the operand sequence and push it onto the stack (push operation).
2. Pop a number from the top of the stack and append it to the output sequence (pop operation).

By applying these two operations in a valid order, you can obtain different output sequences from the input sequence. For example, starting with the sequence 1 2 3, one possible output sequence is 2 3 1.

It turns out that the total number of distinct output sequences that can be obtained is given by the Catalan numbers. The nth Catalan number is given by the formula:

\( C_n = \frac{1}{n+1} \binom{2n}{n} \)

Your task is to compute and output the total number of output sequences for a given n.

inputFormat

The input consists of a single integer n (n ≥ 1), which represents the number of operands in the sequence 1, 2, ..., n.

outputFormat

Output a single integer representing the total number of distinct output sequences that can be obtained by applying the valid stack operations.

sample

1

1