Background

${\rm CYJian}$: “I heard that combining $\gcd$ and $\sum$ is pretty fun?? Then I will...”

Problem Description

${\rm CYJian}$ has been bored recently and started playing with $\gcd$. He came up with a very simple and interesting expression:

$$\prod_{i=1}^N\prod_{j=1}^N\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)}\pmod{104857601}$$

${\rm CYJian}$ has already computed the value of this expression. Now please help him verify it. ${\rm CYJian}$ only gives you $0.2\textrm{s}$ of time.

2024.5.11 upd: The time and memory limits have been relaxed.

Input Format

One line with a positive integer $N$.

Output Format

One line with a positive integer, the value of the answer modulo $104857601$.

5

585494

Hint

Sample explanation:

$\frac{\operatorname{lcm}}{\gcd}$	1	2	3	4	5
1	1	2	3	4	5
2	2	1	6	2	10
3	3	6	1	12	15
4	4	2	12	1	20
5	5	10	15	20	1

For $30\%$ of the testdata: $1 \leq N \leq 5000$.

For $100\%$ of the testdata: $1 \leq N \leq 1000000$.

Translated by ChatGPT 5