【问题描述】

小L有一座环形花园，沿花园的顺时针方向，他把各个花圃编号为1~N(2<=N<=10^15)。他的环形花园每天都会换一个新花样，但他的花园都不外乎一个规则，任意相邻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

【样例输入1】

10 5 3

【样例输出1】

458

【样例输入2】

6 2 1

【样例输出2】

18

【数据规模】

40%的数据中，N<=20；

60%的数据中，M=2；

80%的数据中，N<=10^5。