Time Limit: 1 s
Memory Limit: 128 MB

Submission：25
AC：8
Score：99.49

An evil professor has just assigned you the following problem.

A sequence is defined by the following recurrence:

Determine

.

Input consists of a number of lines, each containing one integer, a value of *i*, no less than zero and no greater than one million. Input is followed by a single line containing the integer *-1*. This last line is not a value of *i* and should not be processed.

For each value of *i* in the input (but not the final `-1`), output the corresponding value of *x _{i}* modulo 1000000.

input

0
-1

output

1