Counting Binary Search Trees (Catalan Numbers)

Given an integer n, count the number of distinct binary search trees (BSTs) with n distinct nodes, such that an in-order traversal will yield a sorted sequence of node values from 1 to n. This problem is equivalent to calculating the n-th Catalan number. The Catalan numbers can be defined by the formula:

$$C(n) = \sum_{i=0}^{n-1} C(i) \cdot C(n-1-i)$$

with the base cases:

$$C(0) = 1,\quad C(1) = 1$$

Your task is to implement a program that reads an integer from standard input and prints the corresponding Catalan number (which is the answer for the BST counting problem) to standard output.

inputFormat

The input consists of a single line containing one integer n (where n is non-negative) representing the number of nodes in the BST.

outputFormat

Output a single integer which is the n-th Catalan number, representing the number of distinct BSTs that can be formed.

## sample

1

1

</p>