Number of Unique Binary Search Trees

In this problem, you are given a single integer ( n ) representing the number of nodes. Each node is uniquely labeled with an integer from 1 to ( n ). You are required to compute the number of distinct binary search trees (BSTs) that can be formed using these nodes. A binary search tree is a binary tree in which for each node, the keys in the left subtree are less than the node’s key, and the keys in the right subtree are greater than the node’s key. It can be shown that the answer for a given ( n ) is the ( n )-th Catalan number, where the Catalan numbers are given by the formula: [ C(n) = \frac{1}{n+1} \binom{2n}{n} ] For example, when ( n = 3 ), there are 5 different BSTs that can be formed. Your task is to implement a program that reads ( n ) from standard input and prints the corresponding number of unique BSTs to standard output.

inputFormat

Input is given via standard input and consists of a single integer ( n ) (where ( n \geq 0 )), which represents the number of nodes in the binary tree.

outputFormat

Output a single integer that represents the number of unique binary search trees that can be formed using nodes labeled from 1 to ( n ). The answer should be printed to standard output.## sample

0

1