Probability of a Good Painting

Oliver is a little yellow duck who not only finds bugs but also loves to paint. His latest painting has n parts, each painted in a distinct color. After receiving criticism for its predictability, Oliver decides to modify his painting over t iterations. In each iteration he does the following:

1. He uniformly randomly selects an index \(i\) \(1\le i\le n\) and notes the color in part \(i\).
2. He uniformly randomly selects an index \(j\) \(1 o n\). Then he paints part \(j\) in the same color as part \(i\). (If part \(j\) already had that color, no change occurs.) Note that \(i\) can be equal to \(j\).

After t iterations the painting is said to be good if it contains at least k distinct colors. Help Oliver compute the probability that the final painting is good.

Observation: Notice that the only parts which contribute to the distinct colors in the final painting are those parts which were never chosen as a target (index \(j\)) in any iteration. Indeed, if a part is ever chosen as a target, its original color is overwritten. Thus, the problem reduces to finding the probability that at least k parts are never selected as a target over the t iterations.

The total number of target selections is \(t\) where each selection is an independent uniform choice among the n parts. For each part, the probability of not being chosen in one iteration is \(\frac{n-1}{n}\) so in \(t\) iterations it is \(\left(\frac{n-1}{n}\right)^t\). However, these events are dependent among the parts. To compute the exact probability that exactly \(r\) parts are never chosen as targets, one may count the number of sequences of target indices which result in a given set of parts never being chosen and all the others chosen at least once. A standard combinatorial argument shows that the probability is given by

[ P(\text{exactly } r \text{ parts are never chosen}) = \frac{\binom{n}{r} ; (n-r)!; S(t, n-r)}{n^t}, ]

where \(S(t, n-r)\) denotes the Stirling numbers of the second kind. Finally, the probability that the painting is good is

[ P(\text{good}) = \sum_{r=k}^{n} \frac{\binom{n}{r} ; (n-r)!; S(t, n-r)}{n^t}. ]

For the purpose of implementation, it is easier to re-parameterize by letting \(m = n - r\), which gives

[ P(\text{good}) = \sum_{m=0}^{n-k} \frac{\binom{n}{m}; m!; S(t, m)}{n^t}. ]

Note: When \(t=0\) (i.e. no iterations), the painting remains unchanged, so the answer is 1 if \(n\ge k\) and 0 otherwise.

inputFormat

The input consists of three space‐separated integers:

• \(n\) \(\ge 1\): the number of parts in the painting (initially all colored differently).
• \(t\) \(\ge 0\): the number of iterations.
• \(k\) \(1 \le k \le n\): the minimum number of distinct colors required for the painting to be considered good.

outputFormat

Output the probability that the final painting is good. Your answer will be accepted if its absolute or relative error does not exceed \(10^{-6}\). (Print the result as a floating point number.)

sample

3 1 2

0.7777777778