Fox Labeling

Time limit3sMemory limit512 MB

Summary

Given n foxes with their initial colors and a label size k, find the expected minutes until every pair of foxes becomes distinguishable by repeatedly labeling random k-subsets.

Level: Hard8 of 10
Topics: Probability, Combinatorics, Dynamic programming
Solved: No attempts yet

Problem

Bytica works in the biological expedition. She has $n$ colored foxes for experiments. There is a problem, however: foxes of the same color are absolutely indistinguishable.

Bytica wants to mark the foxes with colored labels. She repeats the following steps until every pair of foxes becomes distinguishable:

Select a color that has not been used yet (not even as the natural color of some fox).
Get $k$ random foxes from the cage. Each subset of size $k$ is equally likely to be chosen.
Mark each of them with a label of the selected color.

Each procedure (three steps) takes exactly one minute.

Two foxes are distinguishable if their colors differ or the sets of colors of their labels differ.

Bytica is unsure only about the expected time before all foxes become pairwise distinguishable. Write a program that computes this value.

Input

Input consists of two lines. The first line contains two integers $n$ and $k$ ( $1 \le k < n \le 30$ ). The second line contains $n$ integers. The $i$ -th integer is the initial color of the $i$ -th fox.

Colors are positive integers not exceeding 1000.

Output

Print one real number: the expected time in minutes before every pair of foxes becomes distinguishable. The answer is correct if its relative or absolute error is within $10^{-6}$ .

Examples2

Example 1
Input
```
2 1
20 20
```
Expected output
```
1.000000
```
Example 2
Input
```
2 1
15 1000
```
Expected output
```
0.000000
```