Định nghĩa $f(x)$ là số lượng số nguyên $y$ thỏa mãn $1 \leq y\leq x$ và $\gcd(x,y)=1$. Ở đây, $\gcd(x,y)$ là ước chung lớn nhất của $x$ và $y$.

Định nghĩa $g(x) = k \cdot f(x)$.

Định nghĩa $g^{(t)}(x)=g(g^{(t-1)}(x))$ khi $t>1$, và $g^{(1)}(x)=g(x)$.

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

Dữ liệu vào

Dòng duy nhất chứa ba số nguyên $n,k,t$ ($1 \leq n,k,t \leq 998\,244\,352$).

Dữ liệu ra

In ra một số nguyên, là kết quả lấy modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

5 3 4

Dữ liệu ra 1

12

Dữ liệu vào 2

114514 1919 810

Dữ liệu ra 2

565299374