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 $ ).

输入输出样例

输入样例 #1

4 2

输出样例 #1

5

输入样例 #2

3 2

输出样例 #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 $ .