# Jumps

A bunny has to pass n meters with jumps of lengths 3, 2 or 1 meters. In how many different ways this can be done, if the lengths of successive jumps form a non-increasing sequence?

Write program jumps, which computes the number we are looking for.

### Input

The value of n should be entered from the standard input (1 <= n <= 10^{9}).

### Output

The program should write to the standard output one integer, equal to the remainder of the found number, divided by 1000000.

Remark: In 50% of test cases, n <= 10^{5}.

### Constraints

Time limit: 1 second

Memory limit: 64 megabytes

### Examples

input 6 | output 7 |

Explanation: The number of different ways is 7, and its remainder modulo 1000000 is also 7. The different sequences of jumps are:

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