题目背景

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

5

585494

提示

样例解释：

$\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$。