Alternating Pieces Game

Two players, A and B, have invented a new game played on a $1\times n$ board. There are $k$ pieces placed on the board such that exactly half are white and half are black. The pieces are arranged in increasing order of position, with the leftmost piece being white and the rightmost being black, and adjacent pieces always having different colors.

Player A is allowed to move white pieces and Player B is allowed to move black pieces. However, white pieces cannot move to the left and black pieces cannot move to the right. In a single move, a player may choose one of his pieces and move it by any number of positions from $1$ to $d$. When a piece is moved, it cannot jump over the piece immediately adjacent on its moving side and it must remain within the board.

The players take turns making moves, with player A moving first. A player loses if, when it is their turn, they have no legal move available.

Let the positions of the $k$ pieces be $p_1, p_2, \dots, p_k$ with $1 \le p_1 < p_2 < \cdots < p_k \le n$. Define the internal gaps as $g_i = p_{i+1} - p_i - 1$ for $1 \le i \le k-1$. It turns out that under optimal play, the outcome of the game is determined by the nim-sum (or Grundy value) of these gaps when each gap contributes a value of $g_i \bmod (d+1)$ (this follows from the subtraction game with moves $1, 2, \dots, d$ having Grundy value $g \bmod (d+1)$). Player A has a winning strategy if and only if \[ \bigoplus_{i=1}^{k-1} (g_i \bmod (d+1)) \neq 0. \]

Your task is to count how many initial placements of the pieces (choosing $k$ positions from the $n$ available, with the positions implicitly colored as described) yield a winning position for player A. Note that the placements are defined by the choice of positions, and all configurations satisfying the constraints are considered. For a given configuration, the two extra gaps (before the first piece and after the last piece) do not affect the game outcome; however, they do factor into the total number of configurations. In fact, if we define

[ a_0 = p_1 - 1, \quad a_i = p_{i+1} - p_i - 1 ; (1 \le i \le k-1), \quad a_k = n - p_k, ]

then we have

[ a_0 + a_1 + \cdots + a_{k-1} + a_k = n - k, ]

and for any fixed choice of internal gaps $(a_1, \dots, a_{k-1})$ with total sum $S$, there are exactly $(n-k-S+1)$ ways to choose the border gaps $a_0$ and $a_k$. Thus, the number of winning configurations is given by summing, over all sequences $(a_1, \dots, a_{k-1})$ with $0 \le S \le n-k$ and with \[ \bigoplus_{i=1}^{k-1} (a_i \bmod (d+1)) \neq 0, \]

the product $(n-k-S+1)$ multiplied by the number of sequences with that sum and XOR.

Compute and output this total count.

inputFormat

The input consists of a single line containing three integers $n$, $k$, and $d$, where:

• $n$ is the length of the board,
• $k$ (an even number) is the total number of pieces, and
• $d$ is the maximum number of positions a piece can move in one turn.

outputFormat

Output a single integer: the number of initial configurations that guarantee a win for player A under optimal play.

sample

5 2 1

4