Define $f(x)$ como la cantidad de enteros $y$ tales que $1 \leq y\leq x$ y $\gcd(x,y)=1$. Aquí, $\gcd(x,y)$ es el máximo común divisor de $x$ y $y$.
Define $g(x) = k \cdot f(x)$.
Define $g^{(t)}(x)=g(g^{(t-1)}(x))$ cuando $t>1$, y $g^{(1)}(x)=g(x)$.
Encuentra $g^{(t)}(n) \bmod 998\,244\,353$.
Entrada
La única línea contiene tres enteros $n,k,t$ ($1 \leq n,k,t \leq 998\,244\,352$).
Salida
Imprime un entero, que denota la respuesta módulo $998\,244\,353$.
Ejemplos
Entrada 1
5 3 4
Salida 1
12
Entrada 2
114514 1919 810
Salida 2
565299374