# 2022 年上海市大学生程序设计竞赛 - 十一月赛

C. Math

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}$.

NaN