AT_abc212_g [ABC212G] Power Pair

题目描述

给定一个素数 $P$。

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

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

由于答案可能非常大，请输出答案对 $998244353$ 取模后的结果。

输入格式

输入以以下格式从标准输入给出。

$P$

输出格式

请输出答案对 $998244353$ 取模后的结果。

样例 1

输入

3

输出

4

样例 2

输入

11

输出

64

样例 3

输入

998244353

输出

329133417

说明/提示

限制条件

• $2 \leq P \leq 10^{12}$
• $P$ 是素数

样例解释 1

满足条件的 $4$ 组为 $(x,\ y) = (0,\ 0),\ (1,\ 1),\ (2,\ 1),\ (2,\ 2)$。

由 ChatGPT 4.1 翻译