The same textbook chapter asks for the number of valid balanced-parenthesis arrangements of N pairs — a classic Catalan-number application. Given N pairs of parentheses, print the number of distinct valid combinations, modulo 10^9+7, using the Catalan number formula C(2N,N)/(N+1) computed via modular inverse (not by generating all strings).
Input
One integer N.
Output
Number of valid combinations mod (10^9+7).
Constraints
1 ≤ N ≤ 10^6
Sample Input
3
Sample Output
5
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.