창문 깨기 (Large)

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

악당 $N$명이 이 방에서 모임을 열기로 했다. 기념으로 각자 창문을 하나 골라 돌을 하나씩 던진다. 어떤 창문에 던질지는 다른 사람의 선택과 무관하게 창문 $K$개 중에서 균등한 확률로 고른다. 이미 깨진 창문에 돌을 던지면 돌은 창문을 그대로 통과한다.

방의 주인인 당신은 모임 전에 일꾼 $M$명을 시켜 창문을 더 강화하기로 했다. 일꾼도 각자 창문을 하나 골라 강화하며, 어떤 창문을 고를지는 다른 사람의 선택과 무관하게 창문 $K$개 중에서 균등한 확률로 정한다. 창문은 한 번 강화될 때마다 돌을 한 번 더 견딜 수 있게 된다.

모임이 끝난 뒤에 창문이 한 개 이상 깨져 있을 확률을 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에는 각각 네 정수 $K$, $N$, $M$, $H$가 공백으로 구분되어 주어진다.

제한

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

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 케이스 번호이고, $y$는 창문이 한 개 이상 깨질 확률이다. $y$는 소수점 아래 여덟째 자리까지 반올림해, 소수점 아래 여덟 자리를 항상 채워서 출력한다.

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

첫 번째 케이스에서는 일꾼이 강화한 창문과 돌이 날아간 창문이 같을 때만 창문이 깨지지 않으므로, 깨질 확률은 $2/3$이다.

두 번째 케이스에서는 강화된 창문이 돌 하나를 견디더라도 남은 돌 하나를 견딜 창문이 없으므로, 깨질 확률은 $1$이다.

세 번째 케이스에서는 강화되어 있는 창문 2개는 깨지지 않는다. 남은 창문 하나는 일꾼 두 명 중 누구에게도 강화되지 않은 상태로 돌을 맞을 때만 깨지므로, 확률은 $2/3 \times 2/3 \times 1/3 = 4/27$이다.