购物中心前有一条美丽的小巷,绿树成荫。不幸的是,它必须去为停车场腾出空间。
巷子里的树都排成一排。有 $$$n$$$ 个树木点,索引 $$$0$$$ 是购物中心,索引 $$$n+1$$$ 是道路,索引从 $$$1$$$ 到 $$$n$$$ 是树木点。其中一些是被拍摄的——那里长着同样高度的树木$$$k$$$。每个地点不超过一棵树。
当你在$$$x$$$处砍倒一棵树时,你可以让它向左或向右倒下。如果它落到左边,它会占据从 $$$x-k$$$ 到 $$$x$$$(含)的位置。如果它落在右边,它会占据从 $$$x$$$ 到 $$$x+k$$$(含)的位置。
让巷子里的 $$$m$$$ 树在一些地方生长 $$$x_1, x_2, \dots, x_m$$$。如果一条小巷里所有的 $$$m$$$ 树都可以被砍倒,那么这条小巷就被称为不幸的:
- 没有树倒在购物中心或道路上;
- 每个位置都被不超过一棵倒下的树占据。
计算有 $$$m$$$ 树高度 $$$k$$$ 的不同不幸小巷的数量。如果存在一个点 $$$y$$$,使得一棵树在第一个巷子的 $$$y$$$ 中生长,而在第二个巷子的 $$$y$$$ 中不生长,则认为两条巷子是不同的。
输出对 $$$998\,244\,353$$$ 取模的数字。
输入
唯一的一行包含三个整数 $$$n、m$$$ 和 $$$k$$$ ($$$1 \le m, k \le n \le 3 \cdot 10^5$$$) — 树的点数、树的数量和每棵树的高度。
输出
打印一个整数——有 $$$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