题目描述

又是一节愉快的编程课！秦老师披着大披风，端着水杯，迈着大步走进了教室。顿时，全班安静了下来。

秦老师干咳一声，敲敲黑板，问了同学们一个高大上的问题：

有多少这样的序列 $a$ 满足：

$1 \le a_i \le m$

$|a_i - a_{i-1}| \le k$

$a$ 中有 $n$ 个元素模 $998244353$

cyx 挠了挠头，用手算打表。可惜，大数据他懒得算，也算不出

gch 一看，就狂敲键盘，写了一个 dfs。不看数据范围闭眼交。并说：“这 $120\%$ 对的~” 可是出题人太毒瘤了，三个全是大数据，dfs 爆到了天边去

zjs（即出题人）看到题后，微微一笑：“你们对动态规划一无所知”，随后，他开始涛涛大论地讲起zjs

。。。

gch 和 cyx 都恍然大悟：“哦！我懂了！” 现在，动态规划把问题抛给了你，请你来做一做吧！

输入格式

一行三个整数 $n,m,k$

输出格式

一行一个整数 $ans$，有多少种方案

2 3 1

6

提示

$(1,2)$

$(1,3)$

$(2,1)$

$(2,3)$

$(3,1)$

$(3,2)$

数据范围

$2 \le n \le 1000$

$1 \le m \le 5000$