Description

YJC和大火车是好朋友。 一天，他们觉得无聊，于是大火车对YJC说我们来打隔膜吧。

他们掏出了自己所有的火车，共k个，其中YJC有k/2个 火车，大火车有k/2个火车，他们把火车放在了一条长度为n的直线铁轨上。

从左向右，火车依次属于YJC，大火车，YJC......大火车。他们只能移动自己的火车，并且每个火车既不能移出界，也不能越过这个火车相邻的火车。

现在YJC先操作，每次可以移动1到m个火车，谁不能移动火车谁就输，那么现在YJC想知道有多少种火车的布局可以 使得YJC一定可以赢呢，答案对1e9+7取模。

Format

Input

三个整数n，k，m。

kmod 2 = 0, 1<=m<=k<=n<=10000, k <=1000

Output

一个整数表示答案。

Samples

3 2 1

1