Problem
Slinky< /strong> — một món đồ chơi lò xo được tạo ra vào 1943 tại Hoa Kỳ bởi Richard James Ở nước chúng tôi, nó được gọi đơn giản là Cầu vồng. Tất cả bọn trẻ đều thích thả cô xuống cầu thang, đếm xem ai sẽ đưa cô xuống.
Thường là "Cầu vồng" trong tay trẻ em, nó đi xuống bước tiếp theo, đến bước sau một hoặc sau bước 2. (Ví dụ: nếu Cầu vồng được phóng từ bước thứ 10 thì nó có thể dừng ở bước thứ 9, 8 hoặc 7. )
Giả sử có N bậc trên cầu thang. Xác định số lượng "tuyến đường" có thể Cầu vồng từ đỉnh cầu thang xuống đất.
Đầu vào
Một số duy nhất được nhập \(0 < N < 31\).
Đầu ra
In một số duy nhất — số lượng "tuyến đường" Cầu vồng.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
4 |
7 |