크게 벌기

N명의 사람들이 큰돈을 벌기 위해 다음과 같은 게임에 도전한다.

먼저 N명의 참가자는 서로 격리된다. 이때부터 참가자는 서로 연락하거나 다른 참가자에게 정보를 남길 수 없다. 게임 진행자는 참가자를 한 명씩 N개의 상자가 있는 방으로 안내한다. 상자는 게임이 시작될 때 모두 닫혀 있고, 참가자가 방에 들어올 때마다 진행자는 모든 상자를 닫는다. 각 상자에는 서로 다른 참가자의 이름이 적힌 종이가 들어 있다. 상자의 순서는 게임이 진행되는 동안 바뀌지 않는다. 참가자는 최대 M개의 상자를 열 수 있다. 모든 참가자가 자신의 이름이 적힌 종이가 들어 있는 상자를 열면 그룹이 게임에서 이기고, 그룹의 모든 사람이 큰돈을 받는다. 한 사람이라도 자신의 이름이 적힌 종이가 들어 있는 상자를 열지 못하면 그룹은 게임에서 지고, 아무도 돈을 받지 못한다.

참가자가 모두 상자를 무작위로 고르면 승리 확률은 (M/N)N이다. 하지만 훨씬 더 좋은 방법이 있다.

그 방법을 논하기 전에 몇 가지 개념을 정의하자. P = {p1, p2, ..., pN}를 참가자의 집합, B = {b1, b2, ..., bN}를 상자의 집합이라 하자. f를 B에서 P로 가는 사상으로 정의하여, f(b)는 상자 b에 들어 있는 종이에 적힌 참가자라 하자.

이제 참가자 pi가 다음과 같이 상자를 고른다고 하자.

1. x := i로 둔다.

2. pi가 이미 M개의 상자를 열었으면 실패로 끝낸다.

3. pi가 bx를 연다.

   1. f(bx) = pi이면 성공으로 끝낸다.
   2. f(bx) = pj (i != j)이면 x := j로 두고 2로 간다.

모든 참가자가 위 알고리즘을 따른다고 하면, 게임의 결과는 상자의 초기 순서, 즉 f의 정의에만 달려 있다. g를 P에서 B로 가는 사상으로 정의하여 g(pi) = bi라 하자. 참가자들은 모든 i ∈ {1, 2, ..., N}에 대해 (f○g)k (pi) = pi인 k(≤M)가 존재할 때, 그리고 그때만 게임에서 이긴다.

여러분의 과제는 이 게임의 승리 확률을 계산하는 프로그램을 작성하는 것이다. 상자는 무작위로 배치된다고 가정할 수 있다.

입력은 한 줄로 이루어진다. 공백으로 구분된 두 정수 N과 M (1 ≤ M ≤ N ≤ 1,000)이 이 순서대로 주어진다.

주어진 N과 M에 대해 게임의 승리 확률을 출력한다. 출력값은 소수점 아래 여덟 자리까지 출력하며, 오차가 10-8보다 크면 안 된다.