Problem Description

There are $n$ players playing a dice game using a fair $k$-sided die (the faces are numbered from $1$ to $k$, i.e. each roll results in any value from $1$ to $k$ with probability $\frac{1}{k}$). Initially, every player's score is zero.

In one move, the player with the smallest score rolls the die and adds the result to their score. If at some moment multiple players are tied for the smallest score, then one of them is chosen uniformly at random to take the move.

The game ends when any player's cumulative score reaches $m$ or more. Find the expected number of moves.

Input Format

The only line contains three integers $n$, $k$, $m$ ($1 \le n, k, m \le 10^6$), representing the number of players, the number of faces on the die, and the score needed to win.

Output Format

Output one number: the expected number of moves, taken modulo $M = 10^9 + 7$.

It can be proven that the answer can be written as a rational number $p/q$, where $p$ and $q$ are integers and $q \ne 0 \pmod{M}$. Output the value of $p \cdot q^{-1} \bmod M$. In other words, output the value $x$ such that $0 \le x < M$ and $x \cdot q \equiv p \pmod{M}$.

2 4 3

457031255

Hint

Sample Explanation

There are two players, a four-sided die, and the target score is $3$. On the first roll, if the player rolls $3$ or $4$, the game ends immediately (with probability $\frac{1}{2}$). Otherwise, the second player rolls. Similarly, if they roll $3$ or $4$, the game ends (also with probability $\frac{1}{2}$). If the game still does not end, then with probability $\frac{1}{4}$ both players have $1$ point (case A), with probability $\frac{1}{2}$ one player has $1$ point and the other has $2$ points (case B), and with probability $\frac{1}{4}$ both players have $2$ points (case C).

• Case A: The first player rolls, and with probability $\frac{3}{4}$ the game ends after the third move. If it does not end, the second player rolls, and with probability $\frac{3}{4}$ the game ends after the fourth move. If it still does not end, then the game must end after the fifth move (the player with $2$ points rolls and gains at least $1$ more point).

• Case B: The first player rolls, and with probability $\frac{3}{4}$ the game ends after the third move, and with probability $\frac{1}{4}$ it ends after the fourth move.

• Case C: The game must end after the third move.

Combining the cases above, the total expectation is:

$$\frac{1}{2} \cdot 1 + \frac{1}{4} \cdot 2 + \frac{1}{4} \cdot \left( \frac{1}{4} \cdot \left( \frac{3}{4} \cdot 3 + \frac{1}{4} \cdot \frac{3}{4} \cdot 4 + \frac{1}{4} \cdot \frac{1}{4} \cdot 5 \right) + \frac{1}{2} \cdot \left( \frac{3}{4} \cdot 3 + \frac{1}{4} \cdot 4 \right) + \frac{1}{4} \cdot 3 \right) = \frac{461}{4^4}$$

Since $256^{-1} = 285156252 \bmod M$, and $461 \cdot 285156252 \equiv 457031255 \pmod{M}$, the answer is $457031255$.

Translated by ChatGPT 5