카지노

효빈이가 친구들과 카지노에 갔다. 효빈이를 포함한 일행은 모두 $N$명이다.

카지노에서 하는 게임은 $M$개의 영역으로 나뉜 판 위에서 진행한다. 게임을 시작할 때 각 사람은 칩을 하나씩 받는다.

게임은 $K$개의 라운드로 이루어지고, 한 라운드는 다음 순서를 따른다.

1. 아직 탈락하지 않은 각 플레이어가 $M$개의 영역 중 하나에 자기 칩을 놓는다.
2. 딜러가 $M$개의 영역 중 하나를 같은 확률로 고른다.
3. 딜러가 고른 영역에 칩을 놓은 사람은 모두 탈락한다.

$K$개 라운드가 끝날 때까지 탈락하지 않은 사람은 게임을 이긴 것이다.

일행은 칩을 어디에 놓을지 미리 함께 정할 수 있고, 딜러가 영역을 고른 뒤에는 그 결과를 보고 다음 라운드의 배치를 다시 정할 수 있다. 효빈이와 친구들은 적어도 한 사람이 게임을 이길 확률을 최대로 만들려고 한다.

$N$, $M$, $K$가 주어졌을 때, 일행이 최적으로 게임을 진행했을 때 적어도 한 사람이 게임을 이길 확률을 구하는 프로그램을 작성하시오.

첫째 줄에 $N$, $M$, $K$가 공백으로 구분되어 주어진다. ($1 \le N \le 10^{12}$, $1 \le M, K \le 50$)

첫째 줄에 적어도 한 사람이 게임을 이길 확률을 출력한다. 소수점 아래 일곱째 자리에서 반올림해서, 소수점 아래를 항상 여섯 자리로 채워 출력한다. 확률이 $1$이면 1.000000을, $0$이면 0.000000을 출력한다.

$N = 3$, $M = 2$, $K = 2$인 경우를 보자. 첫 번째 라운드에 1번 영역에 칩 한 개, 2번 영역에 칩 두 개를 놓는다. 확률 $0.5$로 1번 영역이 선택되면 두 사람이 남고, 두 사람이 서로 다른 영역에 칩을 놓으면 항상 적어도 한 명이 이긴다. 확률 $0.5$로 2번 영역이 선택되면 한 사람만 남고, 이 사람이 두 번째 라운드에서 살아남을 확률은 $0.5$이다. 따라서 답은 $0.5 \times 1 + 0.5 \times 0.5 = 0.75$이다.

$N = 1$, $M = 3$, $K = 3$인 경우에는 한 사람만 참가하므로 각 라운드에서 살아남을 확률이 $\frac{2}{3}$이고, 게임을 이길 확률은 $\left(\frac{2}{3}\right)^3$이다.

$N = 4$, $M = 3$, $K = 2$인 경우에는 첫 번째 라운드에 한 영역에 칩 두 개, 나머지 두 영역에 칩 한 개씩 놓는 것이 최적이다. 칩을 두 개 놓은 영역이 선택되어도 두 사람이 남으므로, 두 번째 라운드에 적어도 한 명은 게임을 이길 수 있다.