Success Probability of the Card-Pile Game

Consider the following game. There are $k$ decks, each consisting of $n$ cards numbered $1$ through $n$ (one card per number). Shuffle all $kn$ cards well, then deal them into $n$ piles of $k$ cards each, laid out in a single horizontal row. The $i$-th pile from the left (holding $k$ cards) is called "pile $i$".

The game starts at pile $1$. Draw the top card of the current pile (a drawn card is never returned), and if the number on it is $i$, next draw the top card of pile $i$. Repeat: each time, move to the pile whose number equals the value just drawn and take its top card. If every pile becomes empty, the game succeeds. If some pile still has cards but the pile you must draw from next is empty, the game fails.

If the game fails partway through, you may either stop with a failure, or leave the remaining piles as they are (keeping their pile numbers) and restart. On a restart, the first card is drawn from the leftmost pile that still has cards (its top card is drawn first). After restarting you proceed exactly as before: success if all piles become empty, failure if some pile still has cards but the next pile to draw from is empty.

At most $m$ such restarts are allowed, where $m$ is $0$ or $1$. That is, you either never restart, or restart exactly once. The initial layout of the cards depends on the shuffle. Depending on the layout, the game may succeed without restarting, succeed after restarting, or fail even after restarting. Assuming the deck is shuffled well so that every initial layout is equally likely, we want the probability $p$ that the game succeeds within $m$ restarts. Write a program that expresses $p$ as a decimal and prints it to $r$ decimal places, subject to the following rules.

• If $p \times 10^K$ is an integer for some sufficiently large positive integer $K$, the fractional part eventually becomes all zeros; print those zeros as well. For example, if $p = 3/8 = 0.375$, then for $r = 5$ print 0.37500, and for $r = 2$ print 0.37. Likewise, if $p = 1.0$, then for $r = 3$ print 1.000.
• For example, 0.150000… can also be written as the repeating decimal 0.1499999…, but in such cases use the former form (0.150000…).

The first line contains integers $n$, $k$, $m$, $r$ in this order, separated by spaces, where $1 \le n \le 10000$, $1 \le k \le 100$, $m = 0$ or $m = 1$, and $1 \le r \le 10000$.

Print $p$ formatted by the rules above on one line, followed by a newline.