题目描述

农夫约翰建造了一座有 n 间牛舍的小屋，牛舍排在一条直线上，从左到右编号为 1～n。

但是约翰的 m 头牛对小屋很不满意，只要有两头牛之间的牛舍数量小于 k，它们就会互相攻击。住在同一间牛舍更是不行。

约翰为了防止牛之间互相攻击，有多少种安排牛入住牛舍的方法？答案可能很大，你只需要输出答案除以 $10^{9}+7$ 的余数。

输入格式

三个整数 n,m,k。

输出格式

输出答案除以 $10^{9}+7$ 的余数。

10 3 2

20

10 5 0

252

17 5 3

1

数据范围与约定

1≤n≤5000；m,k≤n。