Magic Gems

Problem Source

Codeforces 1117D.

Problem Description

Reziba has an infinite number of magic gems, each of size $1$ unit. Each magic gem can be decomposed into $m$ ordinary gems, each also of size $1$ unit.

Now Reziba needs to choose some magic gems and decompose some of them, so that the resulting gems exactly fill $n$ units of space. How many different selection-and-decomposition schemes are there? Output the answer modulo $10^9 + 7$. (Two schemes are considered different if the number of chosen magic gems differs, or if the magic gems decomposed differ in their positions within the sequence.)

Input Format

The first line contains two integers $n, m$.

Output Format

Output one integer — the answer modulo $10^9 + 7$.

Sample Input

4 2

Sample Output

5

Constraints

For $100\%$ of the test cases, $1 \le n \le 10^{18}$ and $2 \le m \le 100$.