Halloween sắp tới, Phát dự định sẽ cải trang thành một thứ gì đó thật đáng sợ. Gần đây, Phát vừa bắt đầu học lập trình cơ bản và thấy rằng, không gì đáng sợ hơn các chủ đề về quy hoạch động và cây. Vì vậy, thay vì hóa trang tốn kém, Phát sẽ đưa ra một đề bài kết hợp cả hai yếu tố ấy lại với nhau, quy hoạch động trên cây, để làm những người bạn của mình khiếp vía.

Biết rằng Cây Tìm Kiếm Nhị Phân (Binary Search Tree - BST) là một cây gồm nhiều nút, mỗi nút có nhiều nhất là ~2~ nút con, gọi là nút con trái và nút con phải. Các nút thuộc cây con trái luôn mang giá trị nhỏ hơn nút cha và nút thuộc cây con phải luôn mang giá trị lớn hơn nút cha. Dưới đây là hình minh họa.

Phát sẽ cho bạn số nguyên dương ~n~ là số đỉnh của một BST, các đỉnh mang giá trị từ ~1~ tới ~n~. Hãy cho biết có bao nhiêu cây tìm kiếm nhị phân có thể xây dựng từ các đỉnh này.

Dữ liệu

Nhập từ file bst.inp:

• Một số nguyên ~n~ duy nhất ~(1 \le n \le 2 \times 10^3)~

Kết quả

Xuất ra file bst.out:

• Một số duy nhất là kết quả của bài toán. Biết rằng kết quả có thể rất lớn, vì vậy chỉ cần lấy phần dư sau khi chia cho ~1855180120~

Giới hạn

• Subtask ~1~ ~(20\%)~: ~n \le 6~
• Subtask ~2~ ~(20\%)~: ~n \le 40~
• Subtask ~3~ ~(60\%)~: Không có giới hạn gì thêm.

Ví dụ ~1~

Dữ liệu

1

Kết quả

1

Ví dụ ~2~

Dữ liệu

2

Kết quả

2