763. Count Balanced Parentheses (Catalan, Modulo 10^9+7)

Given a non-negative integer n, return the number of DISTINCT valid strings of EXACTLY n pairs of balanced parentheses, taken modulo 10^9 + 7. This count is the n-th Catalan number C_n. Implement the solution using a recursive formulation: the recurrence C_n = sum over i in [0, n-1] of C_i * C_(n-1-i), with base case C_0 = 1. Use memoization to avoid exponential blowup.

Input: A single non-negative integer n.

Output: Return an integer equal to C_n mod (10^9 + 7).

Examples

Input: 0
Output: 1
Explanation: One valid empty string.

Input: 3
Output: 5
Explanation: ((())), (()()), (())(), ()(()), ()()() -> 5 strings.

Input: 1
Output: 1
Explanation: () is the only valid 1-pair string.

Constraints

• 0 <= n <= 1000

Asked by