Problems
Bracket Sequences I
Bracket Sequences I
Calculate the number of valid bracket sequences of length $n$.
For example, when $n = 6$, there are $5$ sequences:
\begin{lstlisting}[language=C++]
()()()
()(())
(())()
((()))
(()())
\end{lstlisting}
\InputFile
One integer $n~(1 \le n \le 10^6)$.
\OutputFile
Print the number of sequences modulo $10^9 + 7$.
Input example #1
6
Output example #1
5