小球染色1

题目描述

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

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

输入格式

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

输出格式

一个整数，表示答案。

样例数据

input

3 3 0

output

3

input

3 2 1

output

4

样例解释：假设有黄和绿两种颜色，4种涂色方案为： 1.黄+绿+绿 2.黄+黄+绿 3.绿+黄+黄 4.绿+绿+黄

数据规模与约定

$1 \leq n,m \leq 2000, 0\leq k \leq n-1$

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

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