Đi lên cầu thang

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 một 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.

Input

Đọc từ tệp văn bản CAU4.INP một số nguyên dương \(n\).

Output

Ghi ra tệp văn bản CAU4.OUT một số duy nhất là số cách đi lên cầu thang khác
nhau mà chú thỏ có thể thực hiện được. Nếu số cách đi có nhiều hơn sáu chữ số thì chỉ ghi sáu chữ số cuối cùng của nó (mod 1000000).

Example

6

7

Scoring

Có \(20\%\) số điểm có \(1 ≤ n ≤ 10^2\)

Có \(30\%\) số điểm có \(10^2 < n ≤ 5 × 10^3\)

Có \(50\%\) số điểm có \(5 × 10^3 < n < 10^6\)