← 返回题目列表

AtCoder · maximum_cup_2018_f

F. 献立表制作

中文机器翻译题面 查看原题

配点 : 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

您可能无法制作菜单。