Breaking Windows (Small)

A room is surrounded by $K$ windows. A window breaks when it takes enough stones. $H$ of the windows are already reinforced, so each of them survives the first stone and breaks on the second one. The other $K - H$ windows are not reinforced and break on the first stone.

Before the meeting the owner of the room hires $M$ workers to reinforce the windows further. Each worker picks one window and reinforces it once, and every reinforcement lets that window survive one more stone. A worker's choice is independent of the other workers, and each of the $K$ windows is equally likely.

Once the reinforcement is done, $N$ villains gather in the room and each of them picks one window and throws one stone at it. A villain's choice is independent of the other villains, and each of the $K$ windows is equally likely. A stone thrown at a window that is already broken passes straight through it.

Compute the probability that at least one window is broken after all the stones have been thrown.

The first line contains the number of test cases $T$. Each of the next $T$ lines holds one test case as four integers.

K N M H

Constraints

• $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$

For each test case print one line in the form Case #x: y. Here $x$ is the test case number starting from 1, and $y$ is the probability that at least one window is broken, rounded to eight decimal places. Always print exactly eight digits after the decimal point, so a value of 0 or 1 is written as 0.00000000 or 1.00000000.

All three cases in the example use a room with three windows.

In the first case, $K = 3$, $N = 1$, $M = 1$, $H = 0$, the room survives only when the villain throws at the window the worker reinforced, so the probability of a break is $2/3$.

In the second case, $K = 3$, $N = 2$, $M = 1$, $H = 0$, one window may be reinforced and survive the first stone, but no window survives a second stone. The probability is $1$.

In the third case, $K = 3$, $N = 1$, $M = 2$, $H = 2$, the two pre-reinforced windows cannot break to a single stone. The remaining window breaks when neither worker picks it and the stone hits it, so the probability is $2/3 \times 2/3 \times 1/3 = 4/27$.