[Sdoi2011]黑白棋

小 A 和小 B 又想到了一个新的游戏。

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

小 A 只能移动白色棋子，并且白色棋子只能向右移动；小 B 只能移动黑色棋子，并且黑色棋子只能向左移动。两人轮流操作，每次当前玩家可以选择 $1$ 至 $d$ 个自己的棋子，将每个被选中的棋子沿规定方向移动任意正整数格。移动后，棋子不能越过其他棋子，也不能移出棋盘。

小 A 先手。轮到某位玩家时，如果不存在合法操作，则该玩家失败。

请计算有多少种初始棋子布局能使小 A 获胜。

输入格式

输入共一行，包含三个整数 $n,k,d$。

输出格式

输出一个整数，表示小 A 获胜的初始布局总数。答案对 $10^9+7$ 取模。

样例输入

10 4 2

样例输出

182

数据范围

• $1\le d\le k\le n\le 10^4$；
• $k$ 为偶数；
• $k\le 100$。

来源与许可

本题为 SDOI 2011 试题「黑白棋」，题面与测试数据整理自 BZOJ。

样例 1

输入

10 4 2

输出

182