Căn - log - sin (sqrt log sin)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Dãy được xác định bởi $x_0=1$ và, với $i>0$, $x_i=x_{\lfloor i-\sqrt{i}\rfloor}+x_{\lfloor\ln i\rfloor}+x_{\lfloor i\sin^2 i\rfloor}$. Góc của hàm sin tính theo radian. Hãy tính $x_i$ modulo $1{,}000{,}000$.

Input

Dòng duy nhất chứa $i$.

Output

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

Subtask

• Subtask 1 — 20 điểm: 0 <= i <= 1000. Mức này dành cho cách trực tiếp hoặc đệ quy nhỏ.
• Subtask 2 — 30 điểm: 0 <= i <= 100000. Mức này yêu cầu nhận ra trạng thái DP và loại bỏ tính toán lặp.
• Subtask 3 — 50 điểm: 0 <= i <= 1000000. Đây là toàn bộ giới hạn của bài.

Ví dụ

Input

0

Output

1

Giải thích

Theo định nghĩa cơ sở, $x_0=1$.