伐木

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

购物中心与马路之间有一条直线形的小巷。购物中心位于位置 $0$，马路位于位置 $n+1$，位置 $1$ 到 $n$ 可以种树。每个位置至多种一棵树，所有树的高度均为 $k$。

砍倒位置 $x$ 的树时，可以选择让它向左或向右倒下。向左倒下会覆盖区间 $[x-k,x]$ 内的所有整数位置；向右倒下会覆盖区间 $[x,x+k]$ 内的所有整数位置。

一条种有 $m$ 棵树的小巷称为“不幸的小巷”，当且仅当可以为每棵树选择一个倒下方向，使得：

• 没有树覆盖位置 $0$ 或位置 $n+1$；
• 任意位置至多被一棵倒下的树覆盖。

请计算不同的不幸小巷数量。两条小巷不同，当且仅当存在某个位置在其中一条小巷种了树，而在另一条小巷没有种树。

答案对 $998\,244\,353$ 取模。

输入格式

输入一行三个整数 $n,m,k$，分别表示可种树的位置数、树的数量和树高。

输出格式

输出一个整数，表示不幸小巷的数量对 $998\,244\,353$ 取模后的结果。

样例输入 1

6 1 4

样例输出 1

4

样例输入 2

5 2 2

样例输出 2

0

样例输入 3

6 2 2

样例输出 3

4

样例输入 4

15 3 2

样例输出 4

311

数据范围

$1\le m,k\le n\le 3\cdot 10^5$。