Define $f(x)$ as the number of integers $y$ such that $1 \leq y\leq x$ and $\gcd(x,y)=1$. Here, $\gcd(x,y)$ is the greatest common divisor of $x$ and $y$.

Define $g(x) = k \cdot f(x)$.

Define $g^{(t)}(x)=g(g^{(t-1)}(x))$ when $t>1$, and $g^{(1)}(x)=g(x)$.

Find $g^{(t)}(n) \bmod 998\,244\,353$.

Input

The only line contains three integers $n,k,t$ ($1 \leq n,k,t \leq 998\,244\,352$).

Output

Output an integer, denoting the answer modulo $998\,244\,353$.

Examples

Input 1

5 3 4

Output 1

12

Input 2

114514 1919 810

Output 2

565299374