在古老的跳蚤国文化中，锅占据着神圣的地位。它不仅是比赛的常客，还是出题人【】的体现。对于比赛的参与者，他们经常能遇到比赛中新鲜出炉的、千奇百怪的小锅、中锅和大锅。按照传统，把锅分给别人是保全自身的最好手段。但如果 “不小心” 把锅扣到无关人员头上，可能会被视为对他人的不敬。

跳蚤国一共有 $k$ 位管理员，现在他们准备举办一场比赛。赛前的工作被分成了 $n$ 个部分，每个部分都有可能出锅。锅一共分为 $m$ 种，且每个部分出每种锅都有可能。

在赛前最后的检查中，没有发现任何一个锅。但在赛后，每个部分都被发现有恰好一种锅。于是管理组要给赛前工作的每个部分找一个背锅的管理员，每个管理员被分到的部分都需要构成一个区间。

显然，一个管理员的责任大小只和他背的 不同的锅种类数 有关。为了避免争执，管理组希望所有管理员背的不同的锅种类数都相同。

设第 $i$ 部分出的锅种类为 $a_i$，那么我们称这个序列是好的当且仅当存在一种把序列 $a$ 划分成 $k$ 个区间的方式，使得每个区间不同的锅种类数都相同。

请你帮管理组求出，$m^n$ 个可能的 $a$ 序列中有多少个是好的，答案对 $998244353$ 取模。

输入格式

输入一行三个正整数 $n,m,k$。

输出格式

输出一行一个整数表示答案。

5 4 2

772

下面是几种可能的填法：

• 填成 $1,1,2,2,2$：一种划分方案为 $[1,2]$ 和 $[3,5]$。第一位管理员背的不同的锅种类数为 $1$（锅的种类为 $\{1\}$），第二位管理员背的不同的锅种类数为 $1$（锅的种类为 $\{2\}$），所有管理员背的不同的锅种类数相同。
• 填成 $3,1,3,1,2$：一种划分方案为 $[1,3]$ 和 $[4,5]$。第一位管理员背的不同的锅种类数为 $2$（锅的种类为 $\{1,3\}$），第二位管理员背的不同的锅种类数为 $2$（锅的种类为 $\{1,2\}$），所有管理员背的不同的锅种类数相同。
• 填成 $3,1,4,3,2$：无论如何划分，都无法使两位管理员背的不同的锅种类数相同。

数据范围

$1\leq k \leq n \leq 2\times 10^5$，$1\leq m \leq 10^8$。

时间限制：$\texttt{4s}$

空间限制：$\texttt{2GB}$