(cauthang.*)

Sở thú có một cầu thang gồm \(n\) bậc dẫn từ bờ suối lên đỉnh đồi. Một chú thỏ có thể thực hiện 1 bước nhảy lên được 1 bậc hoặc 2 bậc hoặc 3 bậc của cầu thang. Lần nào đi lên cầu thang này, chú thỏ đều thực hiện trình tự các bước nhảy sao cho bước nhảy lần sau không ít bậc hơn bước nhảy trước đó.

Yêu cầu: Đếm số lượng các cách đi lên cầu thang khác nhau mà chú thỏ có thể thực hiện được. Biết rằng hai cách đi được xem là khác nhau nếu có ít nhất một bước nhảy khác nhau.

Dữ liệu vào:

+ Một số nguyên dương \(n\ (n \leq 10^{6})\).

Kết quả:

+ Một số nguyên duy nhất cho biết kết quả bài toán, nếu kết quả có nhiều hơn 6 chữ số thì chỉ ghi 6 chữ số cuối cùng của nó.

Ví dụ:

Giải thích: Với \(n = 6\) chú thỏ có các cách đi khác nhau: 1+1+1+1+1+1; 1+1+1+1+2; 1+1+1+3; 1+1+1+1+2+2; 1+1+2+2+2; 3+3; 2+2+2+2;

Ràng buộc:

+ Có 20% số test tương ứng 20% số điểm có \(1 \leq n \leq 10^{2}\);

+ Có 30% số test khác tương ứng 30% số điểm có \(n \leq 5 \times 10^{3}\).

+ Có \(50\%\) số test còn lại tương ứng \(50\%\) số điểm không có ràng buộc gì thêm.