Description

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 Format

Input three numbers $n,k,d$.

Output Format

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

10 4 2

182

Hint

• 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