2165: 花园
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
小L有一座环形花园，沿花园的顺时针方向，他把各个花圃编号为1~N(2<=N<=1015)。他的环形花园每天都会换一个新花样，但他的花园都不外乎一个规则，任意相邻M(2<=M<=5,M<=N)个花圃中有不超过K(1<=K<M)个C形的花圃，其余花圃均为P形的花圃。
例如，N=10,M=5,K=3。则
CCPCPPPPCC 是一种不符合规则的花圃；
CCPPPPCPCP 是一种符合规则的花圃。
请帮小L求出符合规则的花园种数Mod 1000000007
由于请您编写一个程序解决此题。
输入
一行，三个数N,M,K。
输出
花园种数Mod 1000000007
样例输入 复制
10 5 3样例输出 复制
458提示
【样例输入2】
6 2 1
【样例输出2】
18
【数据规模】
40%的数据中，N<=20；
60%的数据中，M=2；
80%的数据中，N<=105。