A dice game is played by $n$ players using a fair $k$-sided die with faces numbered 1 to $k$ (meaning a roll results in any value from 1 to $k$ with probability $\frac{1}{k}$). Initially, each player has zero points.

In a single turn, the player with the fewest points rolls the die and adds the result to their total points. If at any moment there is more than one player with the minimum number of points, one of them is chosen at random to move.

The game ends when any player accumulates $m$ or more points. Determine the expected number of turns.

Input

The first and only line of input contains three integers $n, k, m$ ($1 \le n, k, m \le 10^6$), representing the number of players, the number of sides on the die, and the number of points required to win, respectively.

Output

The output should contain a single number representing the expected number of turns, printed modulo $M = 10^9 + 7$.

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

Examples

Input 1

2 4 3

Output 1

457031255

Note

Explanation of the example: We have two players, a four-sided die, and a limit of 3 points. In the first roll, the game ends if the player rolls a 3 or 4 (i.e., with probability $\frac{1}{2}$). If not, the second player rolls in the second turn. The game also ends if they roll a 3 or 4 (again $\frac{1}{2}$). If not, there is a $\frac{1}{4}$ chance that both players have 1 point (case A), $\frac{1}{2}$ that one has 1 and the other has 2 (case B), and $\frac{1}{4}$ that both have 2 points (case C).

Case A: The first player rolls, $\frac{3}{4}$ chance the game ends in the third turn. If not, the second player rolls, $\frac{3}{4}$ chance the game ends in the fourth. If not, the game ends in the fifth turn (the player with 2 points rolls, they will certainly add at least 1).

Case B: The first player rolls, $\frac{3}{4}$ chance the game ends in the third turn, $\frac{1}{4}$ in the fourth.

Case C: The game definitely ends in the third turn.

In total, we get:

$$\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}{44}$$

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