3839 - 花园

小 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。

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

• 对于 100\% 的数据，保证 2 \leq n \le 10^{15}，2 \leq m \leq \min(n, 5)，1 \leq k \lt m。

luogu