Casino

Hyobin went to a casino with friends. The group, Hyobin included, has $N$ people.

The game is played on a board divided into $M$ areas. When the game starts, every person receives one chip.

The game runs for $K$ rounds, and one round goes like this.

1. Every player who has not been eliminated places their chip on one of the $M$ areas.
2. The dealer picks one of the $M$ areas, each with the same probability.
3. Everyone whose chip is on the area the dealer picked is eliminated.

A person who is not eliminated during the $K$ rounds wins the game.

The group can agree on where to place the chips beforehand, and after the dealer picks an area they can see the result and rearrange their chips for the next round. Hyobin and the friends want to maximize the probability that at least one person wins.

Given $N$, $M$, and $K$, write a program that computes the probability that at least one person wins when the group plays optimally.

The first line contains $N$, $M$, and $K$, separated by spaces. ($1 \le N \le 10^{12}$, $1 \le M, K \le 50$)

Print the probability that at least one person wins. Round it at the seventh decimal place and always print exactly six digits after the decimal point. Print 1.000000 when the probability is $1$ and 0.000000 when it is $0$.

Take $N = 3$, $M = 2$, $K = 2$. In the first round, put one chip on area 1 and two chips on area 2. With probability $0.5$ the dealer picks area 1, two people remain, and if those two put their chips on different areas at least one of them always wins. With probability $0.5$ the dealer picks area 2, one person remains, and that person survives the second round with probability $0.5$. The answer is therefore $0.5 \times 1 + 0.5 \times 0.5 = 0.75$.

For $N = 1$, $M = 3$, $K = 3$ only one person plays, so the survival probability of each round is $\frac{2}{3}$ and the probability of winning is $\left(\frac{2}{3}\right)^3$.

For $N = 4$, $M = 3$, $K = 2$ the best first round puts two chips on one area and one chip on each of the other two. Even if the dealer picks the area with two chips, two people remain, so at least one person can win in the second round.