$f(x)$ を、$1 \leq y \leq x$ かつ $\gcd(x,y)=1$ を満たす整数 $y$ の個数と定義する。ただし、$\gcd(x,y)$ は $x$ と $y$ の最大公約数である。
$g(x) = k \cdot f(x)$ と定義する。
$t>1$ のとき $g^{(t)}(x)=g(g^{(t-1)}(x))$ と定義し、$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