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.

Public test cases

**Input**

4 1 2 3 5 10000

**Output**

4 1 1 2 9 681928184

Information

- Author
- Xavier Povill
- Language
- English
- Official solutions
- C++
- User solutions
- C++