102126: [AtCoder]ABC212 G - Power Pair

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

给定质数 $P$,求有多少个整数 $x,y$,满足 - $0\le x,y\le P-1$ - $\exist n\in \mathbb{N},x^n\equiv y\pmod p$ translated by @ternary_tree

Output

分数: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)。


样例输入2

11

样例输出2

64

样例输入3

998244353

样例输出3

329133417

加入题单

上一题 下一题 算法标签: