Mivik 的标题

题目背景

Mivik 现在已经写好了他的书,他现在准备给这本书起个书名去投稿。

题目描述

由于 Mivik 写书是乱敲键盘敲出来的,他准备对书名干同样的事情。Mivik 的键盘上有 $m$ 个不同的按键,对应着 $m$ 个不同的字符。Mivik 决定在这个键盘上**等概率**随机敲 $n$ 次敲出标题。但出于某些原因,Mivik 希望书名中要包含有一个人的名字 $S$。于是 Mivik 来问你,他随机敲出的标题有多大的概率包含有这个名字。 同样的,Mivik 并不喜欢奇形怪状的小数,所以你只需要输出这个概率对 $998244353$ 取模后的值。

输入输出格式

输入格式


第一行三个整数 $n$、$m$、$|S|$,其中 $|S|$ 代表这个名字的长度。 第二行给出 $|S|$ 个整数 $a_i$,代表这个名字。

输出格式


一行一个整数,代表概率对 $998244353$ 取模后的值。

输入输出样例

输入样例 #1

3 2 2
1 1

输出样例 #1

623902721

输入样例 #2

6 3 4
1 2 3 2

输出样例 #2

480636170

说明

### 样例解释 样例一:为方便描述,我们定义键盘上两个按键为 `a` 和 `b`。那么长度为 3 的所有字符串共有 `aaa`、`aab`、`aba`、`abb`、`baa`、`bab`、`bba`、`bbb` 这 8 个,其中包含有指定名字 `aa` 的共有 `aaa`、`aab`、`baa` 这三个,则概率为 $\frac{3}{8}$,取模后得到 623902721。 ### 数据范围 对于全部数据,有 $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):无特殊限制。