P5221 Product

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

${\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.

One line with a positive integer $N$.

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

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