Some parenthesizations P31589

Given a natural number $n$, compute the number of correct parenthesizations with $n$ opening and $n$ closing parentheses, with just one restriction: the substring “)()” is not allowed.

For instance, for $n = 4$ there are four correct parenthesizations: “(((())))”, “(()(()))”, “(())(())” and “()((()))”.

Input

Input consists of several cases, each one with an $n$ between 1 and $10^4$.

Output

For each $n$, print the result modulo $10^9 + 7$.