Hop, Hop

Time limit1sMemory limit128 MB

Summary

Count, modulo 1000000, the number of ways to write n as a non-increasing sequence of jumps of length 1, 2, or 3, for n up to 1e9.

Level: Medium5 of 10
Topics: Math, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

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).

Input

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

Output

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

Hint

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.

3+3
3+2+1
3+1+1+1
2+2+2
2+2+1+1
2+1+1+1+1
1+1+1+1+1+1

Examples6

Example 1
Input
```
6
```
Expected output
```
7
```
Example 2
Input
```
1
```
Expected output
```
1
```
Example 3
Input
```
2
```
Expected output
```
2
```
Example 4
Input
```
3
```
Expected output
```
3
```
Example 5
Input
```
5
```
Expected output
```
5
```
Example 6
Input
```
7
```
Expected output
```
8
```