Timber
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
There is a beautiful alley with trees in front of a shopping mall. Unfortunately, it has to go to make space for the parking lot.
The trees on the alley all grow in a single line. There are $n$ spots for trees, index $0$ is the shopping mall, index $n+1$ is the road and indices from $1$ to $n$ are the spots for trees. Some of them are taken — there grow trees of the same height $k$. No more than one tree grows in each spot.
When you chop down a tree in the spot $x$, you can make it fall either left or right. If it falls to the left, it takes up spots from $x-k$ to $x$, inclusive. If it falls to the right, it takes up spots from $x$ to $x+k$, inclusive.
Let $m$ trees on the alley grow in some spots $x_1, x_2, \dots, x_m$. Let an alley be called unfortunate if all $m$ trees can be chopped down in such a way that:
- no tree falls on the shopping mall or the road;
- each spot is taken up by no more than one fallen tree.
Calculate the number of different unfortunate alleys with $m$ trees of height $k$. Two alleys are considered different if there is a spot $y$ such that a tree grows in $y$ on the first alley and doesn't grow in $y$ on the second alley.
Output the number modulo $998\,244\,353$.
The only line contains three integers $n, m$ and $k$ ($1 \le m, k \le n \le 3 \cdot 10^5$) — the number of spots for the trees, the number of trees and the height of each tree.
Print a single integer — the number of different unfortunate alleys with $m$ trees of height $k$, modulo $998\,244\,353$.
Input
The only line contains three integers $n, m$ and $k$ ($1 \le m, k \le n \le 3 \cdot 10^5$) — the number of spots for the trees, the number of trees and the height of each tree.
Output
Print a single integer — the number of different unfortunate alleys with $m$ trees of height $k$, modulo $998\,244\,353$.
6 1 4
5 2 2
6 2 2
15 3 2
4
0
4
311