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