22600번 - Earn Big 스페셜 저지다국어

문제

A group of N people is trying to challenge the following game to earn big money.

First, N participants are isolated from each other. From this point, they are not allowed to contact each other, or to leave any information for other participants. The game organizer leads each participant, one by one, to a room with N boxes. The boxes are all closed at the beginning of the game, and the game organizer closes all the boxes whenever a participant enters the room. Each box contains a slip of paper on which a name of a distinct participant is written. The order of the boxes do not change during the game. Each participant is allowed to open up to M boxes. If every participant is able to open a box that contains a paper of his/her name, then the group wins the game, and everybody in the group earns big money. If anyone is failed to open a box that contains a paper of his/her name, then the group fails in the game, and nobody in the group gets money.

Obviously, if every participant picks up boxes randomly, the winning probability will be (M/N)^N. However, there is a far more better solution.

Before discussing the solution, let us define some concepts. Let P = {p₁, p₂, ..., p_N} be a set of the participants, and B = {b₁, b₂, ..., b_N} be a set of the boxes. Let us define f, a mapping from B to P, such that f(b) is a participant whose name is written on a paper in a box b.

Here, consider a participant p_i picks up the boxes in the following manner:

1. Let x := i.
2. If p_i has already opened M boxes, then exit as a failure.
3. p_i opens b_x.
   1. If f(b_x) = p_i, then exit as a success.
   2. If f(b_x) = p_j (i != j), then let x := j, and go to 2.

Assuming every participant follows the algorithm above, the result of the game depends only on the initial order of the boxes (i.e. the definition of f). Let us define g to be a mapping from P to B, such that g(p_i) = b_i. The participants win the game if and only if, for every i ∈ {1, 2, ..., N}, there exists k(≤M) such that (f○しろまるg)^k (p_i) = p_i.

Your task is to write a program that calculates the winning probability of this game. You can assume that the boxes are placed randomly.

입력

The input consists of one line. It contains two integers N and M (1 ≤ M ≤ N ≤ 1,000) in this order, delimited by a space.

출력

For given N and M, your program should print the winning probability of the game. The output value should be printed with eight digits after the decimal point, and should not contain an error greater than 10^-8.

제한

힌트