sqrt log sin

Time limit1sMemory limit128 MB

Summary

Precompute x_i for all i up to 10^6 using the given recurrence with floating point floors, then answer each query modulo 10^6.

Level: Medium4 of 10
Topics: Dynamic programming, Math, Implementation, Prefix sum
Solved: No attempts yet

Problem

Dohyun is doing his math homework. The assignment reads as follows.

Consider the sequence defined recursively by

$x_0 = 1$

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

Compute the value of $x_{1000000}$ .

More generally, write a program that, given an integer $i$ , computes $x_i$ . Here $\lfloor y \rfloor$ is the floor of $y$ (the greatest integer not exceeding $y$ ), $\ln$ is the natural logarithm, and the argument of $\sin$ is measured in radians.

Input

The input consists of several test cases, one integer $i$ per line, where $0 \le i \le 10^6$ .

The last line contains $-1$ , which marks the end of the input and must not be processed.

Output

For each given $i$ , print $x_i$ modulo $10^6$ on its own line.

Examples4

Example 1
Input
```
0
-1
```
Expected output
```
1
```
Example 2
Input
```
1
-1
```
Expected output
```
3
```
Example 3
Input
```
2
3
4
5
-1
```
Expected output
```
5
7
13
21
```

Example 4

Input

Expected output