Shaking off all the dust from the past

题目描述

嗨！想我了吗？lhy 又来和 pzr 做游戏了, 不过你放心, 这次不是交互题啦. lhy 初始时会给出一个正整数 n, 而 pzr 会对他进行一些操作.

对于一个正整数 n, 它将会按照以下方式变化(初始时 k=0)：

• 如果 n = 1, 变化结束.
• 如果 n 是奇素数 $n := n^{\phi(n)}, k := k + 1$
• 否则 n 随机变成它的一个因子, $k:=k+1$.

注意：

1. $\phi(n)$ 是欧拉函数, 指 1 ~ n 中与 n 互素的数的个数. 例如 $\phi(3)=2, \phi(6)=2, \phi(10)=4$.
2. 随机变成一个因子, 采用均匀随机, 即 n 的每个因子都将被等可能的选到.
3. 在本题中, 给出的 n 保证是一个素数.

现在, 请你帮助 pzr 计算期望的操作次数 k.

数据格式

输入

一个素数 n.

输出

一个正整数, 表示 k 对 998244353 取模的结果.

样例

输入

2

输出

3

数据范围及约定

$n \le 10^5$ 是一个素数