题目描述

小蓝是工厂里的安全工程师，负责在一条直线上安放危险油桶。

这条直线上有 $n$ 个空位，他需要将若干个油桶放置在这些空位上。为了安全，每两个油桶之间必须至少隔开 $k$ 个空位。

现在小蓝想知道，共有多少种合法的油桶放置方案？（可以一个油桶都不放）

由于答案可能很大，请输出结果对 $10^9 + 7$ 取模。

输入格式

第一行输入两个正整数 $n, k$。$(1 \le n \le 10^6, 1 \le k \le n)$

输出格式

输出一个整数，表示合法的放置方案数，对 $10^9 + 7$ 取模。

样例输入

4 2

样例输出

6

说明

用 1 表示放置油桶，0 表示不放置。

合法的放置方案如下，共 6 种：

0000  
1000  
0100  
0010  
0001  
1001