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

• $0≤x≤P−1$
• $0≤y≤P−1$
• There exists a positive integer $n$ such that $x^n≡y\ (mod\ P)$.

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

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

Print the answer modulo $998244353$.

$2≤P≤10^{12}$
$P$ is a prime number.

4

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