P1393 Mivik's Title.

Mivik has finished writing his book, and now he is preparing to give it a title and submit it.

Since Mivik wrote the book by randomly hitting keys on the keyboard, he plans to do the same for the book title. Mivik's keyboard has $m$ different keys, corresponding to $m$ different characters. Mivik decides to hit keys on this keyboard uniformly at random $n$ times to produce the title. However, for some reason, Mivik wants the title to contain a person's name $S$. Therefore, Mivik asks you: what is the probability that the randomly typed title contains this name. Also, Mivik does not like weird-looking decimals, so you only need to output this probability modulo $998244353$.

The first line contains three integers $n$, $m$, $|S|$, where $|S|$ is the length of this name. The second line gives $|S|$ integers $a_i$, representing this name.

Output one integer in one line, representing the probability modulo $998244353$.

### Sample Explanation In sample 1, for convenience, we define the two keys on the keyboard as `a` and `b`. Then all strings of length 3 are `aaa`, `aab`, `aba`, `abb`, `baa`, `bab`, `bba`, `bbb`, a total of 8 strings. Among them, the ones that contain the given name `aa` are `aaa`, `aab`, `baa`, which is 3 strings, so the probability is $\frac{3}{8}$. Taking it modulo gives 623902721. ### Constraints For all testdata, $1\le |S|\le 10^5$, $|S|\le n\le |S|+10^5$, $1\le m\le 10^8$. Subtask 1 (5 pts): $m=1$. Subtask 2 (20 pts): $1\le n, m\le 250$. Subtask 3 (30 pts): $1\le n, m\le 5000$. Subtask 3 (45 pts): no special constraints. Translated by ChatGPT 5