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

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

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