Magic Gems

### 题目描述 xht37 有很多魔法宝石。每颗魔法宝石可以分解成 $ m $ 颗普通宝石，魔法宝石和普通宝石都占据 $ 1 $ 体积的空间，但普通宝石不能再被分解。 xht37 想要使一些魔法宝石分解，使得所有宝石占据的空间**恰好**为 $ n $ 单位体积。显然，一个魔法宝石分解后会占据 $ m $ 体积空间，不分解的魔法宝石仍占据 $ 1 $ 体积空间。 现在 xht37 想要求出有多少种分解方案，可以让最后得到的宝石**恰好**占据 $ n $ 单位体积。两种分解方案不同当且仅当分解的魔法宝石数量不同，或者是所用的宝石的编号不同。 xht37 当然知道怎么做，但是他想考考你。 ### 输入格式 输入包含两个数字 $ n,m (1 \le N \le 10^{18},2 \le M \le 100)$ 。 ### 输出格式 输出能使宝石占据恰好 $ n $ 体积的方案数。因为方案数实在太大了，请输出方案数 $ \mod 10^9+7 $ 后的结果。 ### 样例解释 该样例中一颗魔法宝石可以分解得到两颗普通宝石，我们的目标是拿到 $ 4 $ 颗宝石。 让我们用 $ 1 $ 代表魔法宝石，$ 0 $ 代表普通宝石。 则存在如下几种方案： * $ 1111 $ ：没有宝石被分解。 * $ 0011 $ ：第一颗宝石分解。 * $ 1001 $ ：第二颗宝石分解。 * $ 1100 $ ：第三颗宝石分解。 * $ 0000 $ ：第一颗和第二颗宝石分解。 因此答案为 $ 5 $ 。

Reziba has many magic gems. Each magic gem can be split into $ M $ normal gems. The amount of space each magic (and normal) gem takes is $ 1 $ unit. A normal gem cannot be split. Reziba wants to choose a set of magic gems and split some of them, so the total space occupied by the resulting set of gems is $ N $ units. If a magic gem is chosen and split, it takes $ M $ units of space (since it is split into $ M $ gems); if a magic gem is not split, it takes $ 1 $ unit. How many different configurations of the resulting set of gems can Reziba have, such that the total amount of space taken is $ N $ units? Print the answer modulo $ 1000000007 $ ( $ 10^9+7 $ ). Two configurations are considered different if the number of magic gems Reziba takes to form them differs, or the indices of gems Reziba has to split differ.

The input contains a single line consisting of $ 2 $ integers $ N $ and $ M $ ( $ 1 \le N \le 10^{18} $ , $ 2 \le M \le 100 $ ).

Print one integer, the total number of configurations of the resulting set of gems, given that the total amount of space taken is $ N $ units. Print the answer modulo $ 1000000007 $ ( $ 10^9+7 $ ).

4 2

5

3 2

3

In the first example each magic gem can split into $ 2 $ normal gems, and we know that the total amount of gems are $ 4 $ . Let $ 1 $ denote a magic gem, and $ 0 $ denote a normal gem. The total configurations you can have is: - $ 1 1 1 1 $ (None of the gems split); - $ 0 0 1 1 $ (First magic gem splits into $ 2 $ normal gems); - $ 1 0 0 1 $ (Second magic gem splits into $ 2 $ normal gems); - $ 1 1 0 0 $ (Third magic gem splits into $ 2 $ normal gems); - $ 0 0 0 0 $ (First and second magic gems split into total $ 4 $ normal gems). Hence, answer is $ 5 $ .