Josh's Burger Dilemma

This problem is a twist on the classical airplane seating paradox. There is a burger shop that offers \(M\) types of burgers. There are \(N\) people in line and the favorite burger of the \(i\)th person is given by \(b_i\) (an integer between 1 and \(M\)). Normally, each person would take the burger of their choice if it is still available. However, the first person forgets his favorite and picks a burger uniformly at random from all \(M\) burgers. For each of the next \(N-2\) people (i.e. persons 2 through \(N-1\)), the following rule is applied:

• If their favorite burger is still available, they take it.
• Otherwise, they pick a burger uniformly at random from the remaining ones.

Finally, the last person, Josh (the \(N\)th person), gets whichever burger remains. Your task is to compute the probability that Josh ends up with his favorite burger \(b_N\). All random choices are assumed to be uniformly distributed over the available burgers at that time.

Note: You can assume that each burger type is available exactly once (i.e. there are exactly \(M\) burgers in total) and the process follows the described rules. In many cases the answer may be expressed in a closed form (for example, when all favorites are distinct the answer is \(\frac{1}{2}\) for \(N > 1\)), but here the favorites \(b_i\) can be arbitrary.

inputFormat

The first line contains two integers \(N\) and \(M\) (with \(1 \le N \le M\)). The second line contains \(N\) integers \(b_1, b_2, \ldots, b_N\), where \(1 \le b_i \le M\), representing the favorite burger type of the \(i\)th person. Note that although every person likes a specific burger, only the first person forgets his choice and picks randomly.

outputFormat

Output a single real number representing the probability that the last person (Josh) gets his favorite burger. Your answer will be accepted if the absolute or relative error does not exceed \(10^{-6}\).

sample

3 3
1 2 3

0.5