SUCULA

Mỗi thanh sô cô la có dạng thanh dài với kích thước $1\times n$ đơn vị, trên thanh sô cô la người ta xẻ các rãnh chia thanh sô cô la theo kích thước $1\times 1$ cho dễ bẻ.

Yêu cầu: Xác định có bao nhiêu cách bẻ thanh sô cô la theo các rãnh đã xẻ thành nhiều phần.

Hai cách bẻ được coi là như nhau nếu chúng cho cùng một bộ độ dài các phần (không quan tâm thứ tự các phần trên thanh). Cách giữ nguyên cả thanh (không bẻ) cũng được tính là một cách.

Ví dụ: thanh sô cô la chiều dài $n=3$, ta có ba cách bẻ:

• Cách 1: bẻ thành $3$ thanh độ dài $1$: $\{1\},\{2\},\{3\}$.
• Cách 2: bẻ thành $2$ thanh, một thanh độ dài $2$: $\{1-2\}$ và một thanh độ dài $1$ là $\{3\}$ (cách bẻ $\{1\},\{2-3\}$ coi như đã tính).
• Cách 3: giữ nguyên cả thanh.

Dữ liệu vào

Chứa duy nhất số nguyên $n$ là chiều dài thanh sô cô la.

Dữ liệu ra

Chứa số cách bẻ tìm được.

Ràng buộc

• $0<n<1001$.
• Có $50\%$ số test có $n<31$.

Ví dụ