Définissons $f(x)$ comme le nombre d'entiers $y$ tels que $1 \leq y \leq x$ et $\gcd(x,y)=1$. Ici, $\gcd(x,y)$ est le plus grand commun diviseur de $x$ et $y$.

Définissons $g(x) = k \cdot f(x)$.

Définissons $g^{(t)}(x)=g(g^{(t-1)}(x))$ lorsque $t>1$, et $g^{(1)}(x)=g(x)$.

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

Entrée

L'unique ligne contient trois entiers $n,k,t$ ($1 \leq n,k,t \leq 998\,244\,352$).

Sortie

Affichez un entier, représentant la réponse modulo $998\,244\,353$.

Exemples

Entrée 1

5 3 4

Sortie 1

12

Entrée 2

114514 1919 810

Sortie 2

565299374