창문 깨기 (Small)

방 하나가 창문 $K$개로 둘러싸여 있다. 창문은 돌을 맞으면 깨진다. 이 가운데 $H$개는 미리 강화되어 있어서 첫 번째 돌은 견디고 두 번째 돌에 깨지고, 나머지 $K - H$개는 강화되어 있지 않아 첫 번째 돌에 깨진다.

모임 전에 방의 주인은 일꾼 $M$명을 불러 창문을 더 강화한다. 일꾼은 각자 창문 하나를 골라 한 번 강화하고, 강화를 한 번 받은 창문은 돌을 하나 더 견딘다. 일꾼이 어느 창문을 고르는지는 다른 일꾼의 선택과 무관하며, 창문 $K$개 가운데 하나를 같은 확률로 고른다.

강화가 끝나면 악당 $N$명이 방에 모여 각자 창문 하나를 골라 돌을 하나씩 던진다. 악당이 어느 창문을 고르는지도 다른 악당의 선택과 무관하며, 창문 $K$개 가운데 하나를 같은 확률로 고른다. 이미 깨진 창문에 던진 돌은 창문을 그대로 통과한다.

돌을 다 던진 뒤에 깨진 창문이 하나 이상일 확률을 구하시오.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어지는 $T$개의 줄에 테스트 케이스가 하나씩, 정수 네 개로 주어진다.

K N M H

제한

• $1 \le T \le 100$
• $1 \le K \le 20$
• $1 \le N \le 30$
• $1 \le M \le 30$
• $0 \le H \le K$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 창문이 하나 이상 깨질 확률을 소수점 아래 여덟 자리까지 반올림한 값이다. 소수점 아래는 항상 정확히 여덟 자리로 적으며, 값이 0이거나 1일 때도 0.00000000, 1.00000000처럼 적는다.

예제의 세 케이스는 모두 창문이 세 개인 방이다.

$K = 3$, $N = 1$, $M = 1$, $H = 0$인 첫 번째 케이스에서는 일꾼이 강화한 창문에 악당이 돌을 던졌을 때만 창문이 버틴다. 그래서 깨질 확률은 $2/3$이다.

$K = 3$, $N = 2$, $M = 1$, $H = 0$인 두 번째 케이스에서는 어떤 창문이 강화되어 첫 번째 돌을 버티더라도 두 번째 돌까지 버티는 창문은 없다. 확률은 $1$이다.

$K = 3$, $N = 1$, $M = 2$, $H = 2$인 세 번째 케이스에서는 미리 강화된 창문 두 개가 돌 하나에 깨질 일은 없다. 남은 창문 하나가 두 일꾼 모두에게 선택받지 못한 채 돌을 맞으면 깨지므로 확률은 $2/3 \times 2/3 \times 1/3 = 4/27$이다.