Mr. Malnar has decided to organize a New Year's Eve party this year and invite his $n$ best friends. Since it is the wildest night of the year, he will give each friend a mushroom that will allow them to turn their ordered margherita pizza into a capricciosa.

Mr. Malnar owns infinitely many mushrooms, and he has labeled each of them with a distinct non-negative integer. Before the party begins, he will put the mushrooms into a bag from which each guest will draw their own mushroom. Unfortunately, he could not find a bag large enough to hold all the mushrooms, and now he cannot decide which mushrooms to put in the bag. After some thought, he made the following decision:

• Before the party begins, there will be exactly $n$ mushrooms in the bag.
• If the bag contains a mushroom labeled $x > 0$, then it must also contain a mushroom labeled $\lfloor \frac{x-1}{k} \rfloor$.

Help Mr. Malnar determine how many different ways he can prepare the bag of mushrooms for the New Year's party.

Note: Since the required number of ways can be very large, you only need to output its remainder when divided by $10^9 + 7$.

Input

The first line contains the natural numbers $n$ ($2 \le n \le 1\,000\,000$) and $k$ ($1 \le k \le 1\,000\,000$).

Output

In the first line, print the required number of ways modulo $10^9 + 7$.

Examples

Input 1

3 2

Output 1

5

Input 2

3 3

Output 2

12

Note

Explanation of the first example: the possible bags are $\{0, 1, 2\}$, $\{0, 1, 3\}$, $\{0, 1, 4\}$, $\{0, 2, 5\}$, and $\{0, 2, 6\}$.