幂对

题目描述

给定一个素数 $P$。

求满足以下条件的整数对 $(x, y)$ 的数量。

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

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

输入格式

输入按以下格式从标准输入给出:

$P$

输出格式

输出答案对 $998244353$ 取模后的值。

样例

3

4

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

11

64

998244353

329133417

数据范围

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