Sau khi học xong buổi đầu tiên về ngoặc tại SFIT, Khiêm đã có kiến thức để làm những bài ngoặc đơn.

Tuy nhiên, Khiêm thắc mắc rằng với số tự nhiên $n$ thì mình có thể tạo được bao nhiêu bộ ngoặc hợp lệ có độ dài $n$.

Bạn hãy giúp Khiêm nhé giải quyết vấn đề này nhé.

Đầu vào

Một số tự nhiên $n$ duy nhất $(1\le n\le {10}^6)$.

Đầu ra

Một số tự nhiên duy nhất là kết quả của bài toán. Trường hợp số quá lớn lấy dư cho $1000000007$.

Ví dụ

Đầu vào:

6

Đầu ra:

5

Giải thích: $5$ dãy ngoặc hợp lệ là:

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