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$ 取模后输出答案。

3

4

11

64

998244353

329133417

提示

$2 \leq P \leq 10^{12}$ $P$ 是素数。满足条件的四对 $(x, y) = (0, 0), (1, 1), (2, 1), (2, 2)$。

标签: AtCoder|abc212G

来源

AtCoder|abc212G