花园

题目描述

小 L 有一座环形花园,沿花园的顺时针方向,他把各个花圃编号为 $1 \sim n$。花园 $1$ 和 $n$ 是相邻的。 他的环形花园每天都会换一个新花样,但他的花园都不外乎一个规则:任意相邻 $m$ 个花圃中都只有不超过 $k$ 个 C 形的花圃,其余花圃均为 P 形的花圃。 例如,若 $n=10$ , $m=5$ , $k=3$ ,则 - `CCPCPPPPCC` 是一种不符合规则的花圃。 - `CCPPPPCPCP` 是一种符合规则的花圃。 请帮小 L 求出符合规则的花园种数对 $10^9+7$ 取模的结果。

输入输出格式

输入格式


只有一行三个整数,分别表示 $n, m, k$。

输出格式


输出一行一个整数表示答案。

输入输出样例

输入样例 #1

10 5 3

输出样例 #1

458

输入样例 #2

6 2 1

输出样例 #2

18

说明

#### 数据规模与约定 - 对于 $40\%$ 的数据,保证 $n \le 20$。 - 对于 $60\%$ 的数据,保证 $m=2$。 - 对于 $80\%$ 的数据,保证 $n \le 10^5$; - 对于 $100\%$ 的数据,保证 $2 \leq n \le 10^{15}$,$2 \leq m \leq \min(n, 5)$,$1 \leq k \lt m$。