sqrt log sin

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

The sequence is defined by $x_0=1$ and, for $i>0$, $x_i=x_{\lfloor i-\sqrt{i}\rfloor}+x_{\lfloor\ln i\rfloor}+x_{\lfloor i\sin^2 i\rfloor}$. The sine argument is in radians. Compute $x_i$ modulo $1{,}000{,}000$.

Input

The only line contains $i$.

Output

Print $x_i$ modulo $1{,}000{,}000$.

Subtasks

• Subtask 1 — 20 points: 0 <= i <= 1000.
• Subtask 2 — 30 points: 0 <= i <= 100000.
• Subtask 3 — 50 points: 0 <= i <= 1000000.

Examples

Input

0

Output

1

Explanation

By the base definition, $x_0=1$.