12422번 - 창문 깨기 (Large) 스페셜 저지

K개의 창문으로 둘러싸인 방이 있다. 창문들은 돌을 맞으면 깨지는데, 창문 중 일부는 강화가 되어 있어 H개의 창문은 첫 번째 돌에는 견디고 두 번째 돌에 깨지며, 나머지는 강화가 되어 있지 않아 첫 번째 돌에 깨진다.

N 명의 악당들이 이 방에서 모임을 가지기로 하였고, 이 모임에서 기념으로 각자 하나씩 창문을 선택해 돌을 하나씩 던지기로 하였다. 이때 각자 어떤 창문에 던질지 결정하는 것은 다른 사람들의 선택에 무관하며, 이미 깨진 창문에 돌을 던질 경우 돌은 그대로 창문을 통과하게 된다..

기본 상태의 창문은 돌 하나나 두 개에 깨지기 때문에, 방의 주인인 당신은 창문들을 강화하기로 결정했다. 그래서 당신은 M 명의 일꾼들을 시켜서 모임 전에 창문을 더 강화하기로 하였다. 각 일꾼도 임의의 창문 하나를 강화하는데, 악당들의 결정과 마찬가지로 각자 어떤 창문을 강화하는지 결정하는 것은 다른 사람들의 결정에 무관하다. 창문을 한 번 강화할 때마다 그 창문은 돌을 한번 더 맞는 것을 견딜 수 있게 된다.

모임 후에 최소한 한 개 이상의 창문이 깨져있을 확률은 얼마일까?

입력의 첫 줄에는 테스트 케이스의 숫자 T가 주어진다. 각 테스트 케이스는 다음과 같이 네 개의 정수로 주어진다.

K N M H

제한

• 모든 수들은 자연수이다.
• 1 ≤ T ≤ 100.
• 1 ≤ T ≤ 200.
• 1 ≤ K ≤ 200.
• 1 ≤ N ≤ 100.
• 1 ≤ M ≤ 100.
• 0 ≤ H ≤ K.

각 테스트 케이스에 대한 출력은 "Case #x: y" 형태로 이루어져야 한다. x는 1부터 시작되는 케이스 번호이고, y는 한 개 이상의 창문이 깨질 확률이다. 10^-6범위의 절대/상대오차는 정답으로 간주된다.

모든 예제의 방에는 3개의 창문이 있다.
1번 예제의 경우, 강화한 창문과 돌을 맞은 창문이 같은 경우에만 창문이 깨지지 않으므로, 창문이 깨질 확률은 2/3이다.
2번 예제의 경우, 어떤 창문이 강화되고, 돌 하나가 그 창문을 때려서 버텼다고 하더라도, 어떤 창문이라도 두 번째 돌을 버틸 수 없으므로, 창문이 깨질 확률은 1이다.
3번 예제의 경우, 두 개의 강화 창문은 깨질 염려가 없다. 다만, 남은 창문 하나가 어느 일꾼에 의해서도 강화되지 않고 돌을 맞았을 경우에는 창문이 깨지므로, 전체적으로 창문이 깨지는 확률은 2/3*2/3*1/3 = 4/27이다.