解题思路

动态规划（DP）

定义 $dp[i][j]$ 表示第 $i$ 天吃菜 $j$（$1\leq j\leq m$）时的合法食谱数。

转移方程

• 第一天可以任意选，$dp[1][j]=1$。

题目内容

小$A$很喜欢做饭,也很喜欢享用自己做的美食，但是小$A$希望每天吃的菜和前一天的口味不同，若两道菜的编号差不小于$k$，则小$A$认为这两道菜的口味是不同的，现在小$A$正在制定未来$n$天的食谐（第一天可以吃任何菜)，请问一共有几种合法的食谱。答案可能很大，输出结果请对$998244353$取模。

换而言之，给定三个数$n,m,k$。请问有几个长度为$n$的序列$a_1,a_2,...a_n$满足：

1.$1≤a_i≤m (1≤i≤n)$

2.$|a_i-a_{i+1}|≥k(1≤i≤n)$

答案对$998244353$取模。

输入描述

输入一行，三个整数$n,m,k$

$1≤n,m≤1000，0≤k<m$

输出描述

输出一行正整数，表示答案

样例1

输入

3 4 2

输出

10