考え方
\begin{aligned}
M^{K^{N}} \pmod{998244353}
\end{aligned}
を計算せよ，という問題．M^{K^{N}} \pmod{998244353}
\end{aligned}
$x^{n}$の形なら繰り返し二乗法で計算できるので，この形に持っていくことを考える．
logなんかをとっても上手くいくはずがない．
$p = 998244353$は素数だから，「フェルマーの小定理」を考えるのが自然．つまり，$p$の倍数出ない整数$a$に対して
\begin{aligned}
a^{p-1} \equiv 1 \pmod{p}
\end{aligned}
が成り立つ．$p \mid M$である場合は，$M^{K^{N}} \equiv 0 \pmod{998244353}$になるから，はじめに弾いておく．a^{p-1} \equiv 1 \pmod{p}
\end{aligned}
$M^{p-1} \equiv 1 \pmod{p}$をつくりたいので，$K^{N} \div p$を計算し，商を$q$，剰余を$r$とする．つまり，
\begin{aligned}
K^{N} = q (p - 1) + r
\end{aligned}
とすればK^{N} = q (p - 1) + r
\end{aligned}
\begin{aligned}
M^{K^{N}} \equiv M^{r} \pmod{p}
\end{aligned}
となる．これは「繰り返し二乗法」で計算できる形である．M^{K^{N}} \equiv M^{r} \pmod{p}
\end{aligned}
$r$をどうやって求めるかが問題だが，上式の意味するところは
\begin{aligned}
r \equiv K^{N} \pmod{p-1}
\end{aligned}
であり，これも「繰り返し二乗法」で計算できる形になっている．r \equiv K^{N} \pmod{p-1}
\end{aligned}
回答例
N, K, M = map(int, input().split()) p = 998244353 if M % p == 0: exit(print(0)) r = pow(K, N, p - 1) print(pow(M, r, p))
