23846번 - 징검다리 건너기 스페셜 저지

문제

일우는 드라마 '오징어 게임'을 보다가 징검다리 건너기라는 게임에 대해 궁금증이 생겼다. 그것은 "징검다리의 길이가 N일 때, K번째로 출발하는 선수가 살아남을 확률은?" 이었다. 수학 문제를 숨 쉬듯이 푸는 일우는 금방 해법을 찾을 수 있었다. 하지만, 호기심이 가득한 일우는 한 줄에 있는 유리의 개수가 2개가 아닌, 3개인 경우에서의 확률도 궁금했고 그 답을 찾지 못해 여러분에게 이 문제를 가져왔다. 여러분들이 해결해야 할 새로운 징검다리 건너기 문제는 아래 내용과 같다.

N개의 줄에 각각 강화 유리 1개와 일반 유리 2개가 있다. 강화 유리는 참가자가 올라가도 깨지지 않고, 일반 유리는 참가자가 올라가는 즉시 깨진다. 각, 참가자는 게임 도중 최대 N번까지 점프할 수 있으며, i번째 점프에는 i번째 줄에 있는 유리 중 하나를 밟아야 한다. 만약, 어떤 점프 이후에 밟은 유리가 일반 유리인 경우, 즉시, 그 유리가 깨지고 게임에서 제거된다. 그 유리를 밟은 참가자 또한 게임에서 탈락된다. N번의 점프 이후에도 게임에서 살아남은 참가자는 자동으로 Safe Zone에 옮겨지며 게임의 상금인 456억원을 받게 된다. 456억원을 받는 참가자가 한 명이 아닐 수 있음에 유의하라.

일반 유리와 강화 유리는 겉모습으로 구분이 안되기 때문에, 참가자들은 누군가가 이미 밟은 유리이거나, 어떤 줄에 남은 유리가 유일하기 전까지는 강화 유리가 어떤 유리인 지 알지 못한다. 반면, 참가자들은 기억력이 좋기 때문에, 어떤 줄에 점프할 때, 그 줄에서 이미 강화 유리임이 밝혀진 유리가 있다면 그 유리만 밟는다.

거액의 상금을 노리고 K명의 사람들이 이 게임에 참가하였다. 각 참가자에게는 1번부터 K번까지 순서대로 번호가 매겨져 있고, 받은 번호는 그 참가자가 출발하는 순서와 같다. 게임은 1번 참가자부터 순서대로 진행된다. i(2 ≤ i ≤ K)번 참가자는 i-1번 참가자가 탈락하거나 Safe Zone에 도달한 뒤부터 이동할 수 있다.

위 그림은 N=4, K=2일 때의 예시이다.

이 게임에서 K번째 참가자가 게임의 상금 456억원을 받을 수 있는 확률을 구하는 프로그램을 작성하라.

입력

두 정수 N(1 ≤ N ≤ 3,000)과 K(1 ≤ K ≤ 456)가 공백으로 구분되어 주어진다.

출력

이 게임에서 K번째 참가자가 456억원을 받는 확률을 출력하라. 모범 답안과의 절대/상대 오차가 10^-6 이하인 경우 정답으로 인정된다.

제한

힌트