Определим $f(x)$ как количество целых чисел $y$, таких что $1 \leq y \leq x$ и $\gcd(x,y)=1$. Здесь $\gcd(x,y)$ — наибольший общий делитель $x$ и $y$.

Определим $g(x) = k \cdot f(x)$.

Определим $g^{(t)}(x)=g(g^{(t-1)}(x))$ при $t>1$, и $g^{(1)}(x)=g(x)$.

Найдите $g^{(t)}(n) \bmod 998\,244\,353$.

Входные данные

Единственная строка содержит три целых числа $n,k,t$ ($1 \leq n,k,t \leq 998\,244\,352$).

Выходные данные

Выведите одно целое число — ответ по модулю $998\,244\,353$.

Примеры

Входные данные 1

5 3 4

Выходные данные 1

12

Входные данные 2

114514 1919 810

Выходные данные 2

565299374