問題文

素数 $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