P5221 Product
题目背景
${\rm CYJian}$：“听说 $\gcd$ 和 $\sum$ 套起来比较好玩？？那我就……”
题目描述
${\rm CYJian}$ 最近闲的玩起了 $\gcd$。他想到了一个非常简单而有意思的式子：
$$\prod_{i=1}^N\prod_{j=1}^N\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)}\pmod{104857601}$$
${\rm CYJian}$ 已经算出来这个式子的值了。现在请你帮他验算一下吧。${\rm CYJian}$ 只给你 $0.2\textrm{s}$ 的时间哦。
2024.5.11 **upd**: 放宽时空限制。
输入格式
一行一个正整数 $N$。
输出格式
一行一个正整数，表示答案模 $104857601$ 的值。
说明/提示
样例解释：
|$\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|
对于 $30\%$ 的数据：$1 \leq N \leq 5000$。
对于 $100\%$ 的数据：$1 \leq N \leq 1000000$。