E. TLE与debuger

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

在一个长度为n的离散的(可以理解成量子化的)时间轴上(左小右大),有k个单位,其中一半为TLE,另一半为debuger,他们交错排布,最左边是一个TLE单位。

TLE单位为了能让大家题目超时,只会向右移动,而debuger单位为了能够AC只会向左移动,而二者不能互相穿越对方。

TLE与debuger轮流移动,由TLE先开始,每次可以有1-d个单位移动任意距离,直至所有单位均不可移动。

如果最后一次移动由TLE完成,那么就要有同学惨遭TLE的折磨了,我们必须阻止TLE的成功,那么在时间轴上,有多少种初始排列,可以保证debuger完成最后一次移动或初始状态就无法移动呢?

输入格式

共一行,三个正整数n,k,d,含义见题目描述。

输出格式

输出能够保证debuger完成最后一次移动的初始排列数,答案对1000000007取模。

样例

样例输入

10 4 2

样例输出

28

数据范围与提示

,k为偶数。

通告标题

通告内容

已知晓