문제

1부터 N까지 번호가 매겨진 박스와 1부터 N 까지 번호가 매겨진 열쇠가 있다. i번째 키는 i번째 박스를 열 수 있다.

다못이는 각각의 박스에 정확하게 하나의 열쇠를 무작위로 넣는다. 각각의 열쇠가 박스에 들어갈 확률은 모두 같다고 가정한다. 그러고 나서 박스를 모두 잠근다. 다못이에게는 M개의 폭탄이 있다. 폭탄은 잠겨져 있는 박스를 파괴하는 역할을 한다. 이때 박스 안에 있는 열쇠는 부서지지 않는다. 다못이는 모든 열쇠를 얻고 싶다. 그래서 다음 전략을 사용하기로 했다.

우선 잠겨져 있는 박스 하나를 선택해서 폭탄으로 파괴하고 열쇠를 얻는다. 각각의 잠겨져 있는 박스가 선택될 확률은 모두 같다. 그 열쇠로 열 수 있는 박스가 있으면 열고, 그 박스 속의 열쇠로 열 수 있는 박스가 있으면 또 열고, 이를 열 박스가 더 이상 없을 때까지 반복한다. 그러고 나서 폭탄이 남았으면 그 폭탄을 이용해서 이 전략을 반복한다.

다못이가 모든 열쇠를 얻을 확률을 구하는 프로그램을 작성하시오.