热兹巴有很多魔法宝石。每个魔法宝石都可以分为 $$$M$$$ 普通宝石。每个魔法(和普通)宝石占用的空间量为 $$$1$$$ 单位。普通宝石是无法分裂的。
Reziba想要选择一组魔法宝石并分割其中一些,因此所得宝石组占用的总空间为$$$N$$$个单位。如果选择并分割魔法宝石,则需要 $$$M$$$ 单位的空间(因为它被分割为 $$$M$$$ 宝石);如果魔法宝石没有被分割,则需要 $$$1$$$ 单位。
Reziba 可以拥有多少种不同的宝石组合配置,使得占用的空间总量为 $$$N$$$ 单位?打印以 $$$1000000007$$$ 为模的答案 ($$$10^9+7$$$)。如果雷兹巴用来形成它们的魔法宝石数量不同,或者雷兹巴必须分割的宝石指数不同,则两种配置被认为是不同的。
输入
输入包含一行,由 $$$2$$$ 整数 $$$N$$$ 和 $$$M$$$ ($$$1 \le N \le 10^{18}$$$, $$$2 \le M \le 100$$$) 组成。
输出
打印一个整数,即所得宝石集的配置总数,假定所占用的总空间量为 $$$N$$$ 单位。打印以 $$$1000000007$$$ 为模的答案 ($$$10^9+7$$$)。
示例
输入 #1
4 2
输出 #1
5
输入 #2
3 2
输出 #2
3
注意
在第一个示例中,每个魔法宝石可以分裂为 $$$2$$$ 普通宝石,并且我们知道宝石总数为 $$$4$$$。
让 $$$1$$$ 表示魔法宝石,$$$0$$$ 表示普通宝石。
您可以拥有的总配置是:
- $$$1 1 1 1$$$(没有宝石分裂);
- $$$0 0 1 1$$$(第一个魔法宝石分裂为 $$$2$$$ 普通宝石);
- $$$1 0 0 1$$$ (第二颗魔法宝石分裂为 $$$2$$$ 普通宝石);
- $$$1 1 0 0$$$(第三颗魔法宝石分裂为$$$2$$$普通宝石);
- $$$0 0 0 0$$$(第一颗和第二颗魔法宝石总共分为 $$$4$$$ 普通宝石)。
因此,答案是 $$$5$$$。