Contest Duration: - (local time) (100 minutes) Back to Home

## E - Integer Sequence Fair Editorial 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.

posted:
last update: