Hop, Hop

A rabbit named Aram, who lives in CTP Village, travels a total of n meters by jumping 3, 2, or 1 meters at a time. Given the distance n that Aram must travel, write a program that counts how many ways Aram can make the trip so that the jump lengths are in non-increasing order (each jump is no longer than the one before it).

The first line contains the distance n to travel. (1 ≤ n ≤ 10^9)

Print the number of ways to make the trip, taken modulo 1000000.

For example, when n = 6 there are the following 7 ways to add 1, 2, and 3 up to 6 with non-increasing jump lengths. Therefore the remainder of 7 divided by 1000000, which is 7, is printed.

1. 3+3
2. 3+2+1
3. 3+1+1+1
4. 2+2+2
5. 2+2+1+1
6. 2+1+1+1+1
7. 1+1+1+1+1+1