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

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

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

Обмеження

• ~1≤n≤10^6~

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

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

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

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

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

6

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

5