Mushroom Master
Time limit1sMemory limit512 MB
Count the n-element sets of nonnegative integers where every element x > 0 forces the presence of floor((x-1)/k), modulo 1e9+7.
- Level
Medium7 of 10
- Topics
- Tree, Dynamic programming, Combinatorics, Math
- Solved
- No attempts yet
Problem
Mr. Malnar has decided to organize a New Year's party this year and invite his n best friends. Since it is the craziest night of the year, he will give each friend one mushroom, with which that friend can turn an ordered pizza margherita into a capricciosa.
Mr. Malnar owns infinitely many mushrooms, each labeled with a different nonnegative integer. Before the party begins, he will put the mushrooms into a bag, and each guest will draw their mushroom from the bag. Unfortunately, he could not obtain a bag large enough to hold all the mushrooms, so right now he cannot decide which mushrooms to put in the bag. After thinking a bit more, he made the following decision:
- Before the party begins, the bag will contain exactly n mushrooms.
- If the bag contains a mushroom labeled x > 0, then it must also contain a mushroom labeled ⌊(x−1)/k⌋.
Help Mr. Malnar and determine in how many different ways he can prepare the bag of mushrooms for the New Year's party.
Note: Since the number of ways can be very large, print only its remainder modulo 109 + 7.
Input
The first line contains the positive integers n (2 ≤ n ≤ 1 000 000) and k (1 ≤ k ≤ 1 000 000).
Output
In the first line, print the number of ways modulo 109 + 7.
Hint
Explanation of the first sample: the possible bags are {0, 1, 2}, {0, 1, 3}, {0, 1, 4}, {0, 2, 5}, and {0, 2, 6}.