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

3

4

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

11

64

998244353

329133417