Ваше завдання полягає в тому, щоб обчислити кількість дійсних послідовностей дужок довжини \(n\).

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

• ()()()
• ()(())
• (())()
• ((()))
• (()())

Обмеження

• \(1≤n≤10^6\)

Формат вхідних даних

Єдиний вхідний рядок містить ціле число \(n\).

Формат вихідних даних

Вивести кількість послідовностей за модулем \(10^9+7\).

Приклад вхідних даних

6

Приклад вихідних даних

5