q939600
覆盖裂缝
普及 编程题题目描述
在某座不知名的山上有一条裂缝,裂缝的长度为 $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$。