Unique Binary Search Trees

Given an integer n, determine the number of unique binary search trees (BSTs) that can be formed using exactly n distinct nodes. This number is given by the nth Catalan number. The Catalan number can be defined with the recurrence relation:

\( C_n = \sum_{i=0}^{n-1} C_i \times C_{n-i-1} \)

with base cases \( C_0 = 1 \) and \( C_1 = 1 \). Note that if n is 0 or negative, the answer is defined as 0.

Your task is to read the input n from stdin and output the calculated number of unique BSTs to stdout.

inputFormat

The input consists of a single line containing one integer n (which may be 0 or a positive integer).

Input is read from stdin.

outputFormat

Output a single integer representing the number of unique BSTs that can be constructed using exactly n distinct nodes. Write the output to stdout.

0

0