该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

彩块（cblk）

题目描述

给定正整数 $N,M,K$。

有 $N$ 个方块从左到右排成一行，每个方块都需要染成 $1$ 到 $M$ 中的一种颜色。若一对相邻方块颜色相同，则称这一对相邻方块为同色对。

请计算同色对数量不超过 $K$ 的染色方案数。由于答案可能很大，请输出答案对 $998244353$ 取模后的结果。

两种染色方案不同，当且仅当存在至少一个位置的方块颜色不同。

输入格式

输入一行，包含三个整数 $N,M,K$。

输出格式

输出一行一个整数，表示合法染色方案数对 $998244353$ 取模后的结果。

样例

样例输入 #1

3 2 1

样例输出 #1

6

样例输入 #2

100 100 0

样例输出 #2

73074801

样例输入 #3

60522 114575 7559

样例输出 #3

479519525

数据范围与约定

对于 $100\%$ 的数据，满足 $1\le N,M\le 2\times 10^5$，$0\le K\le N-1$。