You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

走楼梯

Description

一个楼梯有$n$级，藤藤同学从下往上走，一步可以跨一级，也可以跨两级，也可以跨三级，也可以跨四级，也可以跨五级，也可以跨六级。。。依次类推，最多跨$m$级。问：他走到第$n$级楼梯有多少种走法

Format

Input

第一行两个整数 $n, m$

Output

输出一个整数表示答案，由于答案可能很大，结果对$10^9 + 7$ 取模输出

Samples

样例输入

3 2

样例输出

3

Limitation

1s, 1024KiB for each test case.

对于 $60\%$ 的数据 $n \leq 1000, m = 2$

对于 $100\%$ 的数据 $n \leq 10^7, m \leq 10^5$