Bracket Sequences I

Calculate the number of valid bracket sequences of length $n$.

For example, when $n=6$, there are $5$ sequences:

()()()
()(())
(())()
((()))
(()())

Input

One integer $n(1\le n\le 10^6)$.

Output

Print the number of sequences modulo $10^9+7$.

Examples