An evil professor has just assigned you the following problem. A sequence is defined by the following recurrence: $$ x_0 = 1, $$ $$ x_i = x_{\lfloor i - \sqrt{i} \rfloor} + x_{\lfloor ln(i) \rfloor} + x_{\lfloor i \cdot sin^2(i) \rfloor} $$ For each value $i$ compute the value $x_i$. \InputFile Consists of a number of lines, each containing one integer $i$, no less than $0$ and no greater than $10^6$. 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. \OutputFile For each value of $i$ (but not the final $-1$) output the corresponding value of $x_i$ modulo $10^6$.