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ỏ đang ở bới suối 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 để lên được dỉnh đồi (bậc thứ \(n\)). 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.

Input

• Một số nguyên dương \(n (n≤10^6).\)

Output

• Ghi 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ó.

Ràng buộc

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

• Có 30% số test khác tương ứng 30% số điểm có \(n≤5×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.

Sample Input

6

Sample Output

7

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;