G - Power Pair Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 で割った余りを出力せよ。

入力例 1

3

出力例 1

4

(x, y) = (0, 0), (1, 1), (2, 1), (2, 2) の 4 組が条件を満たします。

入力例 2

11

出力例 2

64

入力例 3

998244353

出力例 3

329133417

Score : 600 points

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