AT_maximum_cup_2018_f 献立表制作
题目描述
埼大君是 Maximum 小学的职员，负责制定学校的午餐菜单。
现在到了需要制作菜单表的时候了，于是埼大君开始思考菜单的安排。
菜单的平衡很重要。如果总是日餐或者总是西餐，学生们会感到厌倦。
因此，首先要决定当天提供的菜单类型。菜单分为以下 $7$ 种：
- 日餐菜单
- 西餐菜单
- 中餐菜单
- 日西混合菜单
- 日中混合菜单
- 西中混合菜单
- 日西中混合菜单
本次需要考虑的是，满足以下条件的 $N$ 天午餐菜单的总数：
“对于任意连续的 $K$ 天，包含同一类型的菜单的天数不超过 $L$ 天。”
这里，如果当天提供的是混合菜单或日西中混合菜单，则视为当天包含了其中所有涉及的类型。
例如，如果当天提供日西混合菜单，则视为当天既有日餐也有西餐。
具体请参见下表。
看到这里，作为组合大师的你突然想到：
“这样的菜单安排一共有多少种可能呢……？？？”
请计算满足上述条件的菜单安排总数。
由于答案可能非常大，请输出对 $1000000007$ 取模后的结果。
## 关于条件的说明
以 $N = 5, K = 5, L = 3$ 为例。
在例 1 中，所有类型（日餐、西餐、中餐）在连续 $5$ 天中都没有超过 $3$ 天，因此满足条件。
而在例 2 中，西餐在连续 $5$ 天中出现了 $4$ 天，因此不满足条件。
| | 第 1 天 | 第 2 天 | 第 3 天 | 第 4 天 | 第 5 天 |
|----|---------|----------------|----------------|----------------|----------------|
| 例1 | 日餐菜单 | 日中混合菜单 | 中餐菜单 | 西餐菜单 | 中餐菜单 |
| 例2 | 西餐菜单 | 日西混合菜单 | 西中混合菜单 | 日餐菜单 | 日西中混合菜单 |
输入格式
输入为一行，格式如下：
> $N$ $K$ $L$
输出格式
请输出满足条件的菜单安排总数，对 $1000000007$ 取模。
说明/提示
## 限制
- $K \leq N \leq 365$
- $2 \leq K \leq 5$
- $1 \leq L \leq K$
菜单可能无法安排出满足条件的方案。
由 ChatGPT 4.1 翻译