Nhiệm vụ của bạn là tính số lượng dãy ngoặc hợp lệ có độ dài ~n~. Ví dụ, khi ~n=6~, có ~5~ dãy:

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

Dữ liệu vào

Dòng duy nhất chứa một số nguyên ~n~.

Kết quả

In ra số lượng dãy modulo ~10^9+7~.

Giới hạn

• ~1 \le n \le 10^6~

Ví dụ

Dữ liệu vào:

6

Kết quả:

5