配点 : 100 点
問題文
埼大君是最大小学的职员,负责给食的献立制作。
因为差不多到了必须制作菜单表的时候了,埼大君决定来考虑菜单表。
菜单的平衡很重要。单纯都是和食的菜单,或者单纯都是西餐的菜单,会让学生感到厌烦。
因此,他首先决定当天要提供的菜单类型。菜单是,
- 日文菜单
- 西餐菜单
- 中文菜单
- 日式和西式混合菜单
- 日中混合菜单
- 中西混合菜单
- 日式、西式、中式混合菜单
可以得到第7类型。
这次我想思考的是``哪一个连续的K我们将在同一天发布包含相同类型的菜单。L天或更短时间”得到满足。N这是每日学校午餐菜单。
在这里,如果您发布混合菜单或混乱菜单,则您将发布该菜单中包含的所有流派。
例如,如果您提供日式和西式混合菜单,那么当天您将同时提供日式菜单和西式菜单。
详情请参阅下表。
现在,正在观看这一切的组合大师你突然想到了。
“你能想到多少种方法......???”
求满足该条件的菜单组合的总数。
请注意,答案可能非常大,因此 请以1000000007余数的形式输出。
关于条件 将其视为
N = 5, K = 5, L = 3。
此时,例子1拥有所有流派(日餐、西餐、中餐) 由于是在5天3天内,因此满足条件。
一方、例2西餐 由于已经出现5天4天,说明不满足条件。
| 1日目 | 2日目 | 3日目 | 4日目 | 5日目 | |
| 例1 | 日文菜单 | 日中混合菜单 | 中文菜单 | 西餐菜单 | 中文菜单 |
| 例2 | 西餐菜单 | 日式和西式混合菜单 | 中西混合菜单 | 日文菜单 | 日式、西式、中式混合菜单 |
制約
- K \leq N \leq 365
- 2 \leq K \leq 5
- 1 \leq L \leq K
入力
输入是按以下格式从标准输入给出的。
N K L
出力
答案 请打印除以1请逐行输出。
入力例 1
3 3 1
出力例 1
6
入力例 2
15 3 2
出力例 2
213221133
1000000007余数的形式输出。
入力例 3
365 5 3
出力例 3
792323641
入力例 4
5 5 1
出力例 4
0
您可能无法制作菜单。