4938. Math

单点时限: 2.0 sec

内存限制: 1024 MB

Cuber QQ’s research interests lie in number theory, especially for greatest common divisor (GCD) and least common multiple (LCM).

He is also an artist, the creator of beautiful things. On his birthday, his friends will send him some positive integer sets as gifts.

Assume Cuber QQ receive a non-empty positive integer set $S={p_1,p_2,\cdots ,p_k}$, if $\gcd(p_1,p_2,\cdots ,p_k)=1$ and $\operatorname{lcm}(p_1,p_2,\cdots ,p_k)=n$, Cuber QQ think it is a beautiful set.

Cuber QQ will give his friends $n$, his friends now want to know the number of non-empty positive integer sets which is beautiful.

输入格式

The only line contains one integer $n$ ($1\le n\le 10^{12}$).

输出格式

The output contains one integer indicating the answer.

Print the answer modulo $998~244~353$.

样例

Input
4
Output
2
Input
100
Output
322

提示

For the first example, all beautiful sets are ${1,4},{1,2,4}$.

17 人解决,28 人已尝试。

17 份提交通过,共有 77 份提交。

5.8 EMB 奖励。

创建: 1 年,10 月前.

修改: 1 年,10 月前.

最后提交: 2 天前.

来源: N/A

题目标签