Một con thỏ cần băng qua một đoạn đường dài N mét, thỏ có ba cách nhảy với các độ dài bước nhảy là 3 mét, 2 mét, 1 mét. Một cách đi đúng của thỏ là dãy các bước nhảy của nó có tổng độ dài bằng n và bước nhảy liền sau không dài hơn bước nhảy liền trước trong dãy bước nhảy của nó.

Yêu cầu: Cho biết số nguyên dương N (1 <= N <= 10^15), hãy tính số cách đi đúng khác nhau của thỏ để đi hết đoạn đường N mét. Số cách đi có thể rất lớn nên kết quả in ra được viết dưới dạng số dư của phép chia kết quả cho 1000000.

Dữ liệu:

Gồm một dòng chứa số nguyên N.

Kết quả:

In ra số nguyên duy nhất là số cách đi đúng của thỏ viết dưới dạng số dư của kết quả chia cho 1000000.

Hạn chế:

•   40% test đầu tiên có N ≤ 1000
•   30% test tiếp theo có 103 < N ≤ 10^9
•   30% test cuối cùng có 109 < N ≤ 10^15

Sample Input

6

Sample Output

7