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.

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: là giữ nguyên cả thanh.

Input

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

Output

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

Sample Input 1

3

Sample Output 1

3

Subtasks

• ~0 < n < 1001~.
• Có 50% số test ~n < 31~.