#5270. 打隔膜

内存限制:128 MiB 时间限制:5 Sec

题目描述

YJC和大火车是好朋友。
一天,他们觉得无聊,于是大火车对YJC说我们来打隔膜吧。他们掏出了自己所有的火车,共k个,其中YJC有k/2个
火车,大火车有k/2个火车,他们把火车放在了一条长度为n的直线铁轨上。从左向右,火车依次属于YJC,大火车
,YJC......大火车。他们只能移动自己的火车,并且每个火车既不能移出界,也不能越过这个火车相邻的火车。
现在YJC先操作,每次可以移动1到m个火车,谁不能移动火车谁就输,那么现在YJC想知道有多少种火车的布局可以
使得YJC一定可以赢呢,答案对1e9+7取模。

输入格式

三个整数n,k,m。
kmod 2 = 0, 1<=m<=k<=n<=10000, k <=1000

输出格式

一个整数表示答案。

样例

样例输入


			
3 2 1

样例输出


			
1

数据范围与提示