### sqrt log sin

Time Limit: 1000 ms
Memory Limit: 65536 KiB

#### Problem Description

An evil professor has just assigned you the following problem.

A sequence is defined by the following recurrence:

Determine *x _{1000000}*.

#### Input

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.#### Output

For each value of

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

#### Sample Input

0 -1

#### Sample Output

1

#### Hint

#### Source

October, 2010 - Waterloo local contest