说明

由于 Mivik 写书是乱敲键盘敲出来的，他准备对书名干同样的事情。Mivik 的键盘上有 $m$ 个不同的按键，对应着 $m$ 个不同的字符。Mivik 决定在这个键盘上等概率随机敲 $n$ 次敲出标题。但出于某些原因，Mivik 希望书名中要包含有一个人的名字 $S$。于是 Mivik 来问你，他随机敲出的标题有多大的概率包含有这个名字。

同样的，Mivik 并不喜欢奇形怪状的小数，所以你只需要输出这个概率对 $998244353$ 取模后的值。

输入格式

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

第二行给出 $|S|$ 个整数 $a_i$，代表这个名字。

输出格式

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

3 2 2
1 1

623902721

6 3 4
1 2 3 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)：无特殊限制。