题目背景

小镇广场上摆着一圈石凳，凳子上坐着编号 $1$ 到 $n$ 的孩子，其中第 $n$ 个孩子与第 $1$ 个孩子相邻而坐。庆典组委会要从这些孩子里挑出恰好 $k$ 个上台领取纪念徽章，可孩子们彼此不太服气：任意两个被挑出的孩子之间，沿环看过去都要至少夹着 $g$ 个没有被挑出的孩子，才算站得够远。

题目描述

把 $1 \sim n$ 这 $n$ 个位置排成一个环，$1$ 号位置与 $n$ 号位置相邻。求选出恰好 $k$ 个位置的方案数，使得对任意两个被选中的位置，沿环的两侧走（每一侧都要满足）都至少夹着 $g$ 个未被选中的位置。

两个方案不同，当且仅当被选中的位置集合不同。方案数对 $10^9 + 7$ 取模。

输入格式

一行三个整数 $n, k, g$。

输出格式

一行一个整数，表示方案数对 $10^9 + 7$ 取模的结果。

输入输出样例 #1

输入 #1

6 2 2

输出 #1

3

输入输出样例 #2

输入 #2

8 2 3

输出 #2

4

输入输出样例 #3

输入 #3

5 2 2

输出 #3

0

说明

样例解释

样例 1：$n = 6$，$k = 2$，$g = 2$。可行的选取为 $\{1, 4\}$、$\{2, 5\}$、$\{3, 6\}$，共 $3$ 种。例如 $\{1, 3\}$ 不行，因为 $1$ 与 $3$ 之间只有 $2$ 号一个没被选中的位置，不足 $g = 2$ 个。

样例 2：$n = 8$，$k = 2$，$g = 3$。可行的选取为 $\{1, 5\}$、$\{2, 6\}$、$\{3, 7\}$、$\{4, 8\}$，共 $4$ 种。

样例 3：$n = 5$，$k = 2$，$g = 2$。任取两个位置，总有一侧只夹着 $1$ 个位置，不足 $g = 2$ 个，故没有方案。

数据范围

• 对于 $30\%$ 的数据，$3 \le n \le 20$；
• 对于 $60\%$ 的数据，$3 \le n \le 5000$；
• 对于 $100\%$ 的数据，$3 \le n \le 2 \times 10^{5}$，$1 \le k \le n$，$1 \le g \le n$。