题目限制

4000 ms 512 M

题目描述

尊贵的 的 wxx 统一了全世界，开创了人类的新纪元。

为了让子民们和 wxx 一样卷， wxx 决定把一年设为 $D$ 天，当中只有一天放假，也就是 wxx 的生日。

然而， wxx 飞升之后，他的继承人却误解了 wxx 的意思，没能继承 wxx 的卷志。每一个继承人登基时都会把自己的生日设为假日，并且如果存在一天，它前后都是假日，那么这天也会被自动设为假日。把**$D$ 天看做一个环，也就是说第一天和第 $D$ 天相邻。**

我们假设每年会换一个继承人，所有人的生日都独立在 $D$ 天中随机。

工作日逐渐减少，人民无所事事。当一年之中只剩下小于等于 $K$ 天工作日的时候，国家终于崩溃了。

天上的 wxx 预料到了这一切。请你帮他算一下，在亡国之前，每一年的权值之和的期望。

定义一年的权值为这一年中假期的总天数的 $t$ 次方。

更加严谨的描述：从初始全都不是假日开始，令计数器 $cnt=0$，一直执行以下操作：

1. 在 $D$ 天中均匀随机一天，把它设为假日。

2. 把两边都是假日的日期也变成假日。

3. 设此时假日的个数为 $s$。如果 $D-s \le K$ 那么退出循环，否则 $cnt+=s^t$ 并返回第一步。

求 $cnt$ 的期望。

输入格式

一行输入三个整数D,K,t。（0≤K≤D≤2000,0≤t≤1e8）

输出格式

输入一行一个数表示答案。结果对998244353取模。

数据范围

对于 $10\%$ 的数据，$D \le 8$；

对于 $20\%$ 的数据，$D \le 20$；

对于 $40\%$ 的数据，$D \le 400$；

另有 $10\%$ 的数据，$K=t=0$；

另有 $10\%$ 的数据，$K=0$；

另有 $10\%$ 的数据，$t=0$；

对于 $100\%$ 的数据，$0 \le K \le D \le 2000, 0 \le t \le 10^8$。

输入样例

输入样例1：
3 1 2
输入样例2：
15 0 0
输入样例3：
18 4 0

输出样例

输出样例1：
499122178
输出样例2：
935376256
输出样例3：
314520021