题目描述

有 $n$ 块田地拍成一排，你需要给所有的田地种上一些农作物，你现在有 $m$ 种农作物，每个农田只能选择其中一种来种植。

现在你想知道有多少个种植方案，能保证方案中所有的田地最多可能有 $k$ 对相邻的田地作物相同，这个答案可能很大，请输出答案模 $998244353$ 的值。

注意：合法的种植方式不一定需要用完 $m$ 种农作物。

输入格式

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

输出格式

输入题目要求的方案数，答案对 $998244353$ 取模。

样例 #1

样例输入 #1

3 2 1

样例输出 #1

6

共有六种方法，分别是：112、121、122、211、212、221 。

样例 #2

样例输入 #2

100 100 0

样例输出 #2

73074801

样例 #3

样例输入 #3

60522 114575 7559

样例输出 #3

479519525

提示

对于 $100\%$ 的数据：

• 输入都是整数
• $1\ \leq\ N,\ M\ \leq\ 2\ \times\ 10^5$
• $0\ \leq\ K\ \leq\ N\ -\ 1$