Score : $600$ points

问题描述

已知一个质数 $P$。

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

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

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

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Given is a prime number $P$.

How many pairs of integers $(x, y)$ satisfy the following conditions?

• $0 \leq x \leq P-1$
• $0 \leq y \leq P-1$
• There exists a positive integer $n$ such that $x^n \equiv y \pmod{P}$.

Since the answer may be enormous, print it modulo $998244353$.

Constraints

• $2 \leq P \leq 10^{12}$
• $P$ is a prime number.

Input

Input is given from Standard Input in the following format:

$P$

Output

Print the answer modulo $998244353$.

Sample Input 1

3

Sample Output 1

4

Four pairs $(x, y) = (0, 0), (1, 1), (2, 1), (2, 2)$ satisfy the conditions.

Sample Input 2

11

Sample Output 2

64

Sample Input 3

998244353

Sample Output 3

329133417

update @ 2024/3/10 09:28:22