Một dãy ngoặc đúng nếu nó được tạo bởi các ký tự ( và ) và tuân thủ quy tắc sau:

• Mỗi dấu ( phải có một dấu ngoặc ) tương ứng đi sau nó.
• Không có vị trí nào dãy mà số ngoặc ) vượt quá số ngoặc ) tính đến vị trí đó.

Cho ~n~ số nguyên dương, hãy đếm xem số lượng dãy ngoặc đúng có độ dài ~2n~ (tức là gồm ~n~ cặp ngoặc).

Yêu cầu:Tính và in ra số lượng dãy ngoặc đúng có độ dài ~2n~.

Input

Một dòng duy nhất chứa số nguyên dương ~n~ - số cặp ngoặc (~1 \leq n \leq 1000~).

Output

Một dòng duy nhất chứa số lượng dãy ngoặc đúng độ dài ~2n~ modulo ~10^9+7~.

Example input 1

3

Example output 1

5

Note 1

• Có 5 dãy ngoặc đúng có độ dài 6: ((())), (()()), (())(), ()(()), ()()().