- Time limit: 1.00 s
- Memory limit: 512 MB
-
()()()
-
()(())
-
(())()
-
((()))
-
(()())
The only input line has an integer $n$.
Output
Print the number of sequences modulo $10^9+7$.
Constraints
- $1 \le n \le 10^6$
Input:
6
Output:
5
()()()
()(())
(())()
((()))
(()())
6
5