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

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

1 секунда

128 мегабайтів

Середня

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

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

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

Вхідні дані

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

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

Приклад 1