### PROBLEM LINK:

**Author:** shay_gan

**Tester:** shay_gan

**Editorialist:** shay_gan

### DIFFICULTY:

EASY-MEDIUM

### PREREQUISITES:

Modular arithmetic

### EXPLANATION:

The question is actually deceptively easy. If we have M lanes and M^K horses,

finding the top two requires the following steps.

- Finding the fastest horse.
- Finding the 2^{nd} fastest.

Since unless we know the fastest, we cannot find the 2^{nd} fastest, it is seen that the 2^{nd} step must necessarily complete after the first. Among M^K horses, finding the fastest is easy - race them M at a time, and the winners move on. Since M^K horses are there and each race eliminates M-1 horses (since only one horse moves on), the required number of races for this part is (M^K-1)/(M-1). No race will have less than M horses, so the solution must be optimal.

Now for the 2^{nd} fastest, we need to compare every horse that came 2^{nd} in a race the fastest won. Clearly there will be K such horses. To find the fastest of these we just need ceiling((K-1)/(M-1)) races.

So the answer is (M^K-1)/(M-1) + ceiling((K-1)/(M-1)).

Note: In general, to implement the ceiling function easily while coding, you can use the fact that ceiling(x/y) = floor((x-1)/y)+1.

Code in Python: Due to no limit on integer length, we can directly find the answer and apply modulo 10^9+7

Code in C++: Must do it stepwise due to storage constraints, but it is faster.

Also, as illustrated in this C++ code, without running the loop to calculate 1+M+M^2+...+M^(k-1), you can directly calculate (M^K-1)/(M-1) by calculating the modular inverse of M-1 under modulo 10^9+7 using Fermatâ€™s Little Theorem. Both solutions would pass though.