q939600

覆盖裂缝

普及 编程题
通过 1 提交 2 通过率 50% 时间 1000ms 内存 128MB 贡献者 CloverOI
🏷 标签 暂无标签
题目描述

在某座不知名的山上有一条裂缝,裂缝的长度为 $n$,现在有无数块长度为 $1$ , $2$ , $…$ , $k$ 的石板,你需要用这些石板覆盖裂缝。

你可以使用长度为 $1$ 到 $k$ 的石板(每种石板数量无限),覆盖裂缝,要求裂缝被完全覆盖,石板之间不能重叠,也不能有空隙。请问有多少种不同的覆盖方法?由于答案可能很大,输出答案对 $10^{9} + 7$ 取模的结果。

输入格式

一行两个整数 $n$ , $k$。

输出格式

一个整数,表示方案数。

输入输出样例
样例 #1
输入
5 2
输出
8
样例 #2
输入
4 3 
输出
7
提示
  • 对于$100\%$的数据,$1\le k, n\le 10^7$。