题目描述

这个游戏是在一个$\red{1 \times n}$的棋盘上进行的，棋盘上有$\red{k}$个棋子，一半是黑色，一半是白色。

最左边是白色棋子，最右边是黑色棋子，相邻的棋子颜色不同。

小奇可以移动白色棋子，提比可以移动黑色的棋子，它们每次操作可以移动$\red{1}$到$\red{d}$个棋子。

每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。

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

输入格式

共一行，三个数，$\red{n，}$$\red{k，}$$\red{d}$。

输出格式

输出小奇胜利的方案总数。答案对$\red{1000000007}$取模

样例

输入样例

10 4 2

输出样例

182

提示

对于$\red{30\%}$的数据，有 $\red{k=2}$。

对于$\red{100\%}$的数据，有$\red{1<=d<=k<=n<=10000, k}$为偶数，$\red{k<=100}$。