An evil professor has just assigned you the following problem. A sequence is defined by the following recurrence:
For each value i compute the value xi.
Consists of a number of lines, each containing one integer i, no less than 0 and no greater than 106. 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 (but not the final −1) output the corresponding value of xi modulo 106.