专心OI - 跳房子

题目背景

Imakf 有一天参加了 PINO2017 PJ 组,他突然看见最后一道题: ![](https://cdn.luogu.com.cn/upload/pic/39659.png ) 他十分蒟蒻,写不出来。 而如今他还是一个蒟蒻,他又看见一道题: ![](https://cdn.luogu.com.cn/upload/pic/39660.png) 他还是写不出来,于是便来请教您。

题目描述

您有 $N$ 个格子,排成一行,从左往右编号为 $1,2,\cdots,N$。您站在 $1$ 号格子的左边无限远,开始从左往右跳,跳到 $N$ 号格子右侧为止。由于您是一位成功的 OIer,您自然长得很胖,所以您的腿部力量也非常大!这使得您跳一次,当前格子到目标格子中间必须至少空出来 $M$ 格,但您可以跳无数格远! 您认为这么跳太没意思了,于是便想计算出有多少种方案可以跳完全程。由于方案可能过多,您会输出方案数量模 $(10^9+7)$ 的值 方案不同当且仅当经过的任一一个格子编号不同。

输入输出格式

输入格式


第一行两个整数 $N,M$。

输出格式


一个整数,表示跳完全程的方案模 $(10^9+7)$。

输入输出样例

输入样例 #1

5 1 

输出样例 #1

13

输入样例 #2

6 2 

输出样例 #2

13

说明

| 测试数据编号 | $N$ | $M$ | | :-----------: | :-----------: | :-----------: | |$1,2$ | $\leq10$ | $=1$ | | $3,4$ | $\leq10^7$ | $=1$ | | $5,6$ | $\leq10^6$ | $=2$ | | $7,8$ | $\leq10^5$ | $=3$ | | $9,10$ | $\leq10^4$ | $=5$ | | $11,12$ | $\leq10^{12}$ | $=1$ | | $13,14$ | $\leq10^{18}$ |$=10$ | | $15\sim20$ | $\leq10^{18}$ | $=15$| 对于 $100\%$ 的数据,满足 $1 \le N \le 10^{18}$。