CF1821F Timber

在一家购物中心前有一条美丽的小巷，巷子两旁种着树。不幸的是，这条小巷必须被拆除，以腾出空间建停车场。 小巷上的树都种在一条直线上。有 $n$ 个种树的位置，编号 $0$ 处是购物中心，编号 $n+1$ 处是马路，编号从 $1$ 到 $n$ 的位置是种树的位置。其中一些位置已经种上了树，这些树的高度都是 $k$。每个位置最多只能种一棵树。 当你在位置 $x$ 砍倒一棵树时，可以让它向左或向右倒下。如果向左倒下，它会占据从 $x-k$ 到 $x$ 的所有位置（包括两端）；如果向右倒下，它会占据从 $x$ 到 $x+k$ 的所有位置（包括两端）。 假设小巷上有 $m$ 棵树，分别种在 $x_1, x_2, \dots, x_m$ 这些位置上。如果满足以下条件，则称这个小巷是不幸的： - 没有任何一棵树倒在购物中心或马路上； - 每个位置最多只被一棵倒下的树占据。 请计算有多少种不同的不幸小巷，其中有 $m$ 棵高度为 $k$ 的树。若两种小巷在某个位置 $y$ 上，一种种了树而另一种没有，则认为它们不同。 请输出方案数对 $998\,244\,353$ 取模后的结果。

一行包含三个整数 $n, m, k$（$1 \le m, k \le n \le 3 \cdot 10^5$），分别表示种树的位置数、树的数量和每棵树的高度。

输出一个整数，表示有多少种不同的不幸小巷，结果对 $998\,244\,353$ 取模。

由 ChatGPT 4.1 翻译