3839 - 花园

讨论

统计

通过次数

提交次数

旧版界面

时间限制 : 1 秒

内存限制 : 128 MB

小 L 有一座环形花园，沿花园的顺时针方向，他把各个花圃编号为 $1 \sim n$ 。花园 $1$ 和 $n$ 是相邻的。

他的环形花园每天都会换一个新花样，但他的花园都不外乎一个规则：任意相邻 $m$ 个花圃中都只有不超过 $k$ 个 C 形的花圃，其余花圃均为 P 形的花圃。

例如，若 $n=10$ , $m=5$ , $k=3$ ，则

请帮小 L 求出符合规则的花园种数对 $10^9+7$ 取模的结果。

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

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

10 5 3

6 2 1

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

luogu