P83839

花园

难度 7 级 初三 动态规划入门 状态压缩 矩阵
讨论 统计 0通过 0提交 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

小 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
输出
458
样例 2
输入
6 2 1
输出
18

提示

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

来源

luogu

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交