彩色积木

题目描述

$N$ 个积木横向排成一列。要给这个积木列涂色。

两个积木列的涂色方式不同,定义为存在某个积木,它被涂上了不同的颜色。

求满足以下条件的积木列涂色方式有多少种:

• 每个积木涂上颜色 $1$ 到颜色 $M$ 中的任意一种颜色。可以有不使用的颜色。
• 相邻积木对中,被涂成相同颜色的组不超过 $K$ 组。

由于答案可能非常大,请输出对 $998244353$ 取模的结果。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$ $K$

输出格式

输出答案。

样例

3 2 1

6

将积木列的涂色方式用颜色的排列字符串表示时,满足条件的涂色方式有 112, 121, 122, 211, 212, 221。

100 100 0

73074801

60522 114575 7559

479519525

数据范围

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