The Catalan numbers are C(0)=1 and C(n) = sum over i of C(i)*C(n-1-i) for i in 0..n-1. They count many structures (balanced bracket sequences of length 2n, full binary trees with n internal nodes, and so on). Output C(n) modulo 1000000007.
Input format
One line: a non-negative integer n.
Output format
One line: C(n) mod 1000000007.
Constraints
- 0 <= n <= 3000