问题描述

给定一个质数 $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