Dãy ngoặc I

Đếm số dãy ngoặc hợp lệ có độ dài $n$.

Một dãy ngoặc hợp lệ là dãy ký tự ( và ) sao cho các ngoặc đóng mở khớp nhau. Ví dụ với $n=6$, có 5 dãy hợp lệ: ()()(), ()(()), (())(), ((())), (()()).

Dữ liệu vào

Một dòng chứa số nguyên $n$.

Dữ liệu ra

In số dãy ngoặc hợp lệ modulo ${10}^9+7$.

Ràng buộc

• $1\le n\le {10}^6$

Ví dụ