P2490 [SDOI2011] Black and White Chess

A and B came up with a new game. The game is played on a $1 \times n$ board. There are $k$ pieces on the board, half black and half white. The leftmost piece is white, the rightmost piece is black, and adjacent pieces have alternating colors.  A may move white pieces, and B may move black pieces. White pieces cannot move left, and black pieces cannot move right. On each turn, they may move $1$ to $d$ pieces. When moving a piece, it cannot cross over neighboring pieces on either side, and it cannot move off the board. Whoever has no legal move loses. A and B take turns, with A moving first. How many initial arrangements of the pieces will make A win?

Input three numbers $n,k,d$.

Output the total number of initial configurations in which A wins. Print the answer modulo $10^9+7$.

- For $30\%$ of the testdata, $k=2$. - For $100\%$ of the testdata, $1 \leq d \leq k \leq n \leq 10^4$, $k$ is even, and $k \leq 100$. Translated by ChatGPT 5