题目描述

这个游戏是在一个 $1\times n$ 的棋盘上进行的，棋盘上有 $k$ 个棋子，一半是黑色，一半是白色。最左边是白色棋子，最右边是黑色棋子，相邻的棋子颜色不同。

小奇可以移动白色棋子，提比可以移动黑色的棋子，它们每次操作可以移动 $1$ 到 $d$ 个棋子。每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。

小奇和提比轮流操作，现在小奇先移动，有多少种初始棋子的布局会使它有必胜策略？

输入格式

共一行，三个数，$n,k,d$。

输出格式

输出小奇胜利的方案总数。答案对 $10^9+7$ 取模。

10 4 2

182

数据规模与约定

对于 $100\%$ 的数据，有 $1\le d\le k\le n\le 10^4$，$k$ 为偶数，$k\le100$。

题目来源

By Hzwer