Definiujemy $f(x)$ jako liczbę liczb całkowitych $y$ takich, że $1 \leq y \leq x$ oraz $\gcd(x,y)=1$, gdzie $\gcd(x,y)$ oznacza największy wspólny dzielnik $x$ i $y$.

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

Definiujemy $g^{(t)}(x)=g(g^{(t-1)}(x))$ dla $t>1$ oraz $g^{(1)}(x)=g(x)$.

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

Wejście

W jedynym wierszu znajdują się trzy liczby całkowite $n,k,t$ ($1 \leq n,k,t \leq 998\,244\,352$).

Wyjście

Wypisz jedną liczbę całkowitą oznaczającą odpowiedź modulo $998\,244\,353$.

Przykłady

Wejście 1

5 3 4

Wyjście 1

12

Wejście 2

114514 1919 810

Wyjście 2

565299374