Nhiệm vụ của bạn là đếm số dãy ngoặc đúng có độ dài ~n~, chia dư cho ~10^9 + 7~.

Dãy ngoặc đúng được định nghĩa như sau:

• Xâu rỗng là dãy ngoặc đúng.
• Nếu xâu ~A~ là dãy ngoặc đúng thì ~(A)~ cũng là dãy ngoặc đúng.
• Nếu ~A~ và ~B~ đều là dãy ngoặc đúng thì ~A + B~ cũng là dãy ngoặc đúng.

Ví dụ (()) và ()(())() là dãy ngoặc đúng, còn (() và (()))(( thì không.

Dữ liệu vào

Dòng đầu tiên và duy nhất chứa một số nguyên ~n~.

Kết quả

In ra số dãy ngoặc đúng có độ dài ~n~, đã chia dư cho ~10^9 + 7~.

Ví dụ

Đầu vào:

4

Đầu ra:

2

Giải thích: Với ~n = 4~ có hai dãy ngoặc đúng là (()) và ()().

Giới hạn

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

Nếu ~n~ là số lẻ thì không có dãy ngoặc đúng nào, đáp án là ~0~.

Nếu ~n = 2m~ thì đáp án là số Catalan thứ ~m~:

~C_m = \dfrac{1}{m+1} \dbinom{2m}{m}~

Hãy tính bằng bảng giai thừa và nghịch đảo modulo. Đừng quên xử lý riêng trường hợp ~n~ lẻ.