CF1117D.Magic Gems

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.

Reziba 拥有许多魔法宝石。每颗魔法宝石可以分裂成 $M$ 颗普通宝石。每颗魔法宝石（以及每颗普通宝石）所占空间均为 $1$ 单位。普通宝石无法再分裂。

Reziba 希望选出若干颗魔法宝石，并对其中一部分进行分裂，使得最终得到的所有宝石所占总空间恰好为 $N$ 单位。若某颗魔法宝石被选中并分裂，则它占据 $M$ 单位空间（因为它分裂成了 $M$ 颗宝石）；若某颗魔法宝石被选中但未分裂，则它仅占据 $1$ 单位空间。

Reziba 有多少种不同的最终宝石集合配置，使得所占总空间恰好为 $N$ 单位？请将答案对 $1000000007$（即 $10^9+7$）取模后输出。若两种配置中 Reziba 所选魔法宝石的总数不同，或 Reziba 进行分裂的宝石下标集合不同，则认为这两种配置不同。

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

输入包含一行，其中为两个整数 $N$ 和 $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$).

输出一个整数，表示在总占用空间恰好为 $N$ 个单位的前提下，最终宝石集合的配置总数。答案对 $1000000007$（即 $10^9+7$）取模。

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

在第一个例子中，每颗魔法宝石可以分裂成 $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$。