Description

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$.

Input Format

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 Format

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

3 2 2
1 1

623902721

6 3 4
1 2 3 2

480636170

Hint

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