题目背景

${\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$的值。

5

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$