카드 더미 게임의 성공 확률

다음과 같은 게임을 생각한다. $1$부터 $n$까지의 수가 하나씩 적힌 $n$장의 카드가 $k$벌 있다. 이 $kn$장의 카드를 잘 섞은 뒤 $k$장씩 나누어 가로로 한 줄로 늘어놓아 $n$개의 더미를 만든다. 이렇게 만든 $n$개의 더미 중 왼쪽에서 $i$번째 더미($k$장짜리)를 "더미 $i$"라고 부른다.

게임은 더미 $1$에서 시작한다. 더미의 맨 위 카드 한 장을 뽑고(뽑은 카드는 더미로 되돌리지 않는다), 그 카드에 적힌 수가 $i$이면 이어서 더미 $i$의 맨 위 카드 한 장을 뽑는다. 이렇게 방금 뽑은 카드에 적힌 수를 번호로 하는 더미의 맨 위 카드를 뽑는 일을 반복한다. 모든 더미의 카드가 없어지면 성공이다. 아직 카드가 남은 더미가 있는데도 다음에 카드를 뽑아야 할 더미가 비어 있으면 실패다.

도중에 실패한 경우에는 그대로 실패로 끝내거나, 남은 카드 더미를 그대로(더미 번호도 그대로) 둔 채 게임을 다시 시작할 수 있다. 게임을 다시 시작할 때 처음 뽑는 카드는 카드가 남아 있는 더미 중 가장 왼쪽 더미에서 뽑는다(그 더미의 맨 위 카드가 처음 뽑히는 카드가 된다). 다시 시작한 뒤에도 이전과 같은 방법으로 진행하여, 모든 더미의 카드가 없어지면 성공이고, 아직 카드가 남은 더미가 있는데도 다음에 뽑아야 할 더미가 비어 있으면 실패다.

이러한 재시작은 최대 $m$번까지 할 수 있으며, $m$은 $0$ 또는 $1$이다. 즉 한 번도 재시작하지 않거나, 딱 한 번만 재시작한다. 게임 시작 전 섞는 방법에 따라 카드의 초기 배치가 달라진다. 당연히 초기 배치에 따라 재시작 없이 성공하기도 하고, 재시작하여 성공하기도 하며, 재시작해도 실패하기도 한다. 충분히 잘 섞었으므로 모든 초기 배치가 같은 확률로 나타난다고 가정하고, 재시작 $m$번 이내에 성공할 확률 $p$를 구하려 한다. 이 확률 $p$를 소수로 나타내어 소수점 아래 $r$번째 자리까지 구해 출력하는 프로그램을 작성하여라. 단 다음 조건을 만족하도록 출력한다.

• 충분히 큰 양의 정수 $K$에 대해 $p \times 10^K$가 정수가 되는 경우, 소수부는 도중부터 $0$이 이어지지만 그 $0$도 함께 출력한다. 예를 들어 $p = 3/8 = 0.375$인 경우 $r = 5$이면 0.37500을 출력하고, $r = 2$이면 0.37을 출력한다. $p = 1.0$인 경우도 마찬가지로, 예를 들어 $r = 3$이면 1.000을 출력한다.
• 예를 들어 0.150000…은 순환소수 0.1499999…로도 나타낼 수 있지만, 이러한 경우에는 앞의 표기(0.150000…)를 사용한다.

첫 줄에 정수 $n$, $k$, $m$, $r$가 이 순서대로 공백으로 구분되어 주어진다. $1 \le n \le 10000$, $1 \le k \le 100$, $m = 0$ 또는 $m = 1$, $1 \le r \le 10000$이다.

위에서 지정한 규칙대로 나타낸 $p$를 한 줄에 출력하고, 그 뒤에 줄바꿈을 넣는다.