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

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