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⁴.

Output

For each n, print the result modulo 10⁹ + 7.