sqrt log sin#1207

sqrt log sin

2 seconds

128 megabytes

Very easy

The evil professor has just given you the following task. Let us define a sequence as follows:

x_{0} = 1,

x_0 = 1,

x_{i} = x_{⌊ i - i ⌋} + x_{⌊ l n (i)⌋} + x_{⌊ i \cdot s i n^{2} (i)⌋}

x_i = x_{\lfloor i - \sqrt{i} \rfloor} + x_{\lfloor \ln(i) \rfloor} + x_{\lfloor i \cdot \sin^2(i) \rfloor}

For each given value of $i$ , compute $x_{i}$ x_i.

Input

The input consists of multiple lines, each containing one integer $i$ ( $0 \leq i \leq 1 0^{6}$ 0 \leq i \leq 10^6). The last line contains $- 1$ and should not be processed.

Output

For each value of $i$ (except the last $- 1$ ), print the corresponding value of $x_{i}$ x_i modulo $1 0^{6}$ 10^6.

Examples

Example 1

Loading

x_{0} = 1,

x_{i} = x_{⌊ i - i ⌋} + x_{⌊ l n (i)⌋} + x_{⌊ i \cdot s i n^{2} (i)⌋}

x_{i}

0 \leq i \leq 1 0^{6}

x_{i}

1 0^{6}