小球染色 2

题目描述

有n个小球排成一行，有m种颜色可以选择给每个小球涂色，但是要求是：要让这些小球最多有k对相邻小球的颜色相同（另一种解释为最多有k个小球与它左边的小球颜色相同，1号左边没有小球），问有多少种涂色方法？

方案数很大，只需要对 998244353 取余即可。

输入格式

三个整数：$n,m,k$

输出格式

一个整数，表示答案。

样例数据

input

3 2 1

output

6

样例解释

样例一解释：共有六种方法，分别是：112、121、122、211、212、221 。

input

100 100 0

output

73074801

数据规模与约定

$1 \leq n,m \leq 2*10^5, 0\leq k \leq n-1$

时间限制：$2 \text {s}$

空间限制：$256 \text {MB}$