Catalan Numbers

Given an integer N, compute the N-th Catalan number modulo 10⁹ + 7. The Catalan numbers appear in many combinatorial problems and are defined recursively as follows:

$C(0)=1$, and $C(n+1)=\sum_{i=0}^{n} C(i)\cdot C(n-i)$

Alternatively, they have a closed-form expression using binomial coefficients:

$C(n)=\frac{1}{n+1}\binom{2n}{n}$

Your task is to write a program that reads an integer from standard input and outputs the corresponding Catalan number modulo 10⁹+7.

inputFormat

The input consists of a single integer N (0 ≤ N ≤ some reasonable limit) provided via standard input.

outputFormat

Output a single integer representing the N-th Catalan number computed modulo 10⁹+7.

0

1