题目描述

Hero 正在为朋友们准备一场聚会。他有一张圆桌，桌边有 $N$ 个座位，编号为 $0,1,\ldots,N-1$。编号相邻的两个座位彼此相邻，同时座位 $N-1$ 与座位 $0$ 也相邻。

恰好会有 $K$ 位朋友参加聚会，而且他们到达的时间两两不同。每当一位新朋友到达时，Hero 必须立即从当前的空座位中选择一个让他坐下。朋友一旦坐下，就不会再移动。Hero 自己不坐在桌边。

定义一个**人群块（cluster）**为一段极大的连续已占用座位。例如，若座位 $3,4,5,6$ 上有人，而座位 $2,7$ 为空，则这四个人构成一个人群块。

Hero 希望在整个入座过程中，任意时刻的人群块数量都不超过 $G$。

不同朋友是可区分的：可以按到达顺序将他们编号为 $1,2,\ldots,K$。如果最终某两种方案中，某位朋友坐在了不同的座位，则视为两种不同的最终配置。

请计算满足要求的最终配置数量，对 $10^9+7$ 取模。

输入格式

一行输入三个整数：

N K G

输出格式

输出一个整数，表示合法最终配置数量对 $10^9+7$ 取模后的结果。

数据范围

$2\le N\le2000$，$1\le K\le N$，$1\le G\le K$。

样例

输入

3 2 1

输出

6

输入

4 2 1

输出

8