#P1357. 花园

    ID: 358 远端评测题 1000ms 125MiB 尝试: 2 已通过: 2 难度: 5 上传者: 标签>动态规划dp福建省历届夏令营矩阵运算状态压缩状压

花园

题目描述

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

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

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

  • CCPCPPPPCC 是一种不符合规则的花圃。
  • CCPPPPCPCP 是一种符合规则的花圃。

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

输入格式

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

输出格式

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

10 5 3
458
6 2 1
18

提示

数据规模与约定

  • 对于 40%40\% 的数据,保证 n20n \le 20
  • 对于 60%60\% 的数据,保证 m=2m=2
  • 对于 80%80\% 的数据,保证 n105n \le 10^5
  • 对于 100%100\% 的数据,保证 2n10152 \leq n \le 10^{15}2mmin(n,5)2 \leq m \leq \min(n, 5)1k<m1 \leq k \lt m