题目描述

小明有很多魔法宝石。每颗魔法宝石可以分割成$\red{M}$颗普通宝石。每个魔法和普通宝石占用的空间都是$\red{1}$ 个单位，且普通宝石不能分割。

小明想要选择一组魔法宝石，并将其中的一部分分割开来，产生一组宝石占用总空间为$\red{N}$个单位。如果 选择并分割一颗魔法宝石，则需要占用$\red{M}$个空间单位（因为它被分割成$\red{M}$颗普通宝石）；否则魔法宝石 需要占用$\red{1}$个单位的空间。

请问小明可以拥有多少不同的宝石序列，使得占用的空间总量为$\red{N}$个单位？答案对$\red{10^9+7}$取模。

如果小明形成它们的魔法宝石的数量不同，或者小明分割魔法宝石的标号不同，则认为这两种序列不 同。

（一句话题意，$\red{a_1+a_2+...+a_k=N}$的方案数，且$\red{a_i\in \{1,M\}}$）

输入格式

一行，两个整数$\red{N,M}$

输出格式

一行，即宝石的方案数。

样例

输入样例

4 2

输出样例

5

提示

样例$\red{1}$的解释：

$\red{1111}$

$\red{0011}$

$\red{1001}$

$\red{1100}$

$\red{0000}$

其中$\red{1}$为魔法宝石，$\red{0}$为普通宝石。所以答案为$\red{5}$

数据范围

对于$\red{50\%}$的数据，$\red{1<=N<=10^3,2<=M<=10^3}$。

对于$\red{100\%}$的数据，$\red{1<=N<=10^{18},2<=M<=100}$。

1117d