Một cầu thang có ~n~ bậc. Mỗi bước có thể nhảy lên ~1~, ~2~ hoặc ~3~ bậc. Số bậc của bước sau không ít hơn bước trước.

Yêu cầu: Đếm số cách đi lên hết cầu thang. Hai cách đi khác nhau nếu tồn tại ít nhất một bước nhảy khác nhau.

Input

Đọc từ file văn bản CAU4.INP một số nguyên dương ~n~ (~1 \le n < 10^6~).

Output

Ghi ra file văn bản CAU4.OUT số cách đi. Nếu kết quả có nhiều hơn ~6~ chữ số thì chỉ ghi ~6~ chữ số cuối cùng.

Scoring

• Subtask ~1~ ~(20\%)~: ~n \le 10^2~.
• Subtask ~2~ ~(30\%)~: ~10^2 < n \le 5 imes 10^3~.
• Subtask ~3~ ~(50\%)~: không có ràng buộc gì thêm.

Example input 1

6

Example output 1

7

Note 1

Với ~n = 6~, các cách đi là ~1+1+1+1+1+1~, ~1+1+1+1+2~, ~1+1+1+3~, ~1+1+2+2~, ~1+2+3~, ~2+2+2~ và ~3+3~.