Дужкові послідовності 1

Підрахуйте кількість правильних дужкових послідовностей довжини $n$.

Наприклад, при $n=6$ існує $5$ послідовностей:

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

Вхідні дані

Одне ціле число $n(1\le n\le 10^6)$.

Вихідні дані

Виведіть кількість правильних дужкових послідовностей за модулем $10^9+7$.

Приклади