220. Generate Parentheses (Count)

Given n pairs of parentheses, return the number of distinct well-formed parentheses strings that can be generated. This equals the n-th Catalan number.

Input: A non-negative integer n.

Output: Integer — count of valid combinations.

Examples

Input: 3
Output: 5
Explanation: 5 valid combinations for n=3.

Input: 1
Output: 1
Explanation: '()'.

Input: 0
Output: 1
Explanation: Empty string is one valid combination.

Constraints

• 0 <= n <= 30

Asked by