该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

Given an integer n, print the sum.

$\sum\limits_{i=1}^n \sum\limits_{j=1}^n\left(\lfloor \frac n{max(i,j)}\rfloor\cdot [ \gcd(i, j)=1] \right) mod (1234657890)$

Format

Input

每行1个$n(\le10^{19})$，不超过10万行。.

Output

每行输出一个和，

Samples

1
2

1
4

Limitation

1s, 1024KiB for each test case.