#P1117D. Magic Gems
-
ID: 4630
Type: RemoteJudge
3000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Magic Gems
No submission language available for this problem.
Description
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$).
Input
The input contains a single line consisting of $2$ integers $N$ and $M$ ($1 \le N \le 10^{18}$, $2 \le M \le 100$).
Output
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$).
Samples
4 2
5
3 2
3
Note
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$.