题目描述

在一个牛村里，每头奶牛恰好拥有一栋房子。这些房子排成一条直线。共有 $N$ 栋房子，它们按照离村中心的距离从近到远编号为 $1$ 到 $N$。

莱迪有很多香蕉——足够所有奶牛吃。今天她非常慷慨，决定把自己的一部分香蕉分给奶牛。

但是，众所周知，香蕉是放射性的。更糟糕的是，莱迪的香蕉尤其具有放射性，因此需要警惕突然冒出的各种麻烦。如果莱迪把很多香蕉放在彼此很近的位置，可能会引起核爆炸，这无疑会损害莱迪的形象。莱迪把香蕉装在小盒子里，每个盒子都能屏蔽香蕉的放射线，只要它们远离奶牛。为了防止核爆炸，莱迪必须按如下规则分配香蕉：

• 每头奶牛得到不超过一个香蕉；
• 不允许超过 $C$ 头住在连续编号房屋中的奶牛都得到香蕉。

例如，当 $N=4$ 且 $C=2$ 时，莱迪可以把香蕉分给第 $1$、第 $2$ 和第 $4$ 栋房子的奶牛，但不能把香蕉分给第 $2$、第 $3$ 和第 $4$ 栋房子的所有奶牛，因为第 $2,3,4$ 栋房子相邻，可能导致核爆炸。

莱迪想知道有多少种方式可以把香蕉分给奶牛。答案对 $1\,000\,000\,007$ 取模。

注意，对可以分给奶牛的香蕉数量没有限制；特别地，莱迪也可以不给任何奶牛香蕉。

输入格式

输入文件唯一一行包含两个正整数 $N$ 和 $C$，分别表示房屋数量，以及在不引发核爆炸的情况下可以同时得到香蕉的连续房屋数量上限。

输出格式

输出一个整数，表示莱迪可以把香蕉分给奶牛的方案数，对 $1\,000\,000\,007$ 取模。

样例

样例 1

4 2

13

样例解释

满足上述规则的房屋编号集合共有 $13$ 个：

$\{1,2,4\}$，$\{1,3,4\}$，$\{1,2\}$，$\{1,3\}$，$\{1,4\}$，$\{2,3\}$，$\{2,4\}$，$\{3,4\}$，$\{1\}$，$\{2\}$，$\{3\}$，$\{4\}$，$\varnothing$。

样例 2

3 1

5

样例解释

满足上述规则的房屋编号集合共有 $5$ 个：

$\{1,3\}$，$\{1\}$，$\{2\}$，$\{3\}$，$\varnothing$。

注意，集合 $\{1,3\}$ 是允许的，因为第 $1$ 栋和第 $3$ 栋房子并不相邻，因此不会发生核爆炸。

样例 3

3 5

8

样例解释

莱迪不需要担心第二条规则，因为连续房屋的数量不足 $5$。

因此，所有 $8$ 个子集都满足规则：

$\{1,2,3\}$，$\{1,2\}$，$\{1,3\}$，$\{2,3\}$，$\{1\}$，$\{2\}$，$\{3\}$，$\varnothing$。

计分方式