G - 幂对

得分：$600$ 分

问题描述

给定一个质数 $P$。

有多少对整数 $(x, y)$ 满足以下条件？

• $0 \leq x \leq P-1$
• $0 \leq y \leq P-1$
• 存在一个正整数 $n$，使得 $x^n \equiv y \pmod{P}$。

由于答案可能很大，输出结果模 $998244353$。

约束

• $2 \leq P \leq 10^{12}$
• $P$ 是一个质数。

输入

从标准输入读入数据，数据格式如下：

$P$

输出

将答案模 $998244353$ 输出。

3

4

满足条件的四对$(x, y)$为$(0, 0), (1, 1), (2, 1), (2, 2)$。

11

64

998244353

329133417