Unique Binary Search Trees

Given an integer n, determine the number of distinct binary search trees (BSTs) that can be formed using nodes numbered from 1 to n. The result is the n-th Catalan number, which can be computed using the formula:

$$C_n = \frac{1}{n+1}\binom{2n}{n}$$

You are required to implement an algorithm that computes this value using dynamic programming.

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 19) provided via standard input.

outputFormat

Output the number of unique binary search trees that can be formed with n nodes. The result should be printed to standard output.

3

5