Balanced Parentheses Strings Count

Given a positive integer n, count the number of different balanced parentheses strings of length 2n. A string of parentheses is called balanced if every opening parenthesis has a corresponding closing parenthesis and they are correctly nested. This number is given by the Catalan number:

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

Since the number can be very large, output the result modulo $10^9+7$.

Examples:

• For n = 3, the output is 5.
• For n = 4, the output is 14.
• For n = 1, the output is 1.
• For n = 5, the output is 42.

inputFormat

The input consists of a single integer n (1 ≤ n), which represents the number of pairs of parentheses. The balanced parentheses strings to be considered are of length 2n.

outputFormat

Output a single integer: the number of different balanced parentheses strings of length 2n modulo $10^9+7$.

3

5