E - Integer Sequence Fair 解説 by en_translator

There are \(K^N\) sequences that will be evaluated; i.e. “a sequence of length \(N\) consisting of integers between \(1\) and \(K\) (inclusive).”
Thus, there are \(M^{(K^N)}\) ways to “give each of the evaluated sequences a score between \(1\) and \(M\).”
Therefore, this problem asks to find the remainder of \(M^{(K^N)}\) divided by \(P := 998244353\).

If \(M\) is a multiple of \(P\), then \(M^{(K^N)}\) is a multiple of \(P\), so we should print \(0\).
Hereinafter we assume that \(M\) is not a multiple of \(P\).

Then, since \(P\) is a prime, by Fermat’s little theorem

\(M^{P-1} \equiv 1 \pmod{P}\)

holds. Therefore, let \(q\) and \(r\) be the quotient and remainder when dividing \(K^N\) by \((P-1)\), respectively, then

\(M^{(K^N)} = M^{(q(P-1)+r)} = (M^{P-1})^q \times M^r \equiv 1^q \times M^r = M^r \pmod{P}\),

so the remainder of \(M^{(K^N)}\) divided by \(P\) is equal to the remainder of \(M^r\) by \(P\).
Hence, in order to find the remainder of \(M^{(K^N)}\) by \(P\), it is sufficient to find the following two values:

  • The remainder \(r\) when dividing \(K^N\) by \((P-1)\), and
  • the remainder when dividing \(M^r\) by \(P\).

These can be computed fast enough by means of fast exponentiation.
Be sure to avoid overflows in the process of computation.