Problem Statement

Given is a prime number P.
How many pairs of integers (x, y) satisfy the following conditions?

• $0 \leq x \leq P-1$
• $0 \leq y \leq P-1$
• There exists a positive integer n such that $x^n \equiv y \pmod{P}$.

Since the answer may be enormous, print it modulo 998244353.

Input

Input is given from Standard Input in the following format:
P

Output

Print the answer modulo 998244353.

Constraints

• $2 \leq P \leq 10^{12}$
• P is a prime number.

Sample Input 1

3

Sample Output 1

4

Four pairs (x, y) = (0, 0), (1, 1), (2, 1), (2, 2) satisfy the conditions.

Sample Input 2

11

Sample Output 2

64

Sample Input 3

998244353

Sample Output 3

329133417

见题面 Input 部分

见题面 Output 部分