박스 안의 열쇠

1부터 N까지 번호가 붙은 박스 N개와 1부터 N까지 번호가 붙은 열쇠 N개가 있다. i번 열쇠는 i번 박스를 열 수 있다.

다못이는 각 박스에 열쇠를 정확히 하나씩 무작위로 넣는다. 가능한 모든 열쇠 배치의 확률은 같다. 그런 다음 모든 박스를 잠근다.

다못이에게는 M개의 폭탄이 있다. 폭탄 하나는 잠긴 박스 하나를 부수며, 박스 안에 있던 열쇠는 손상되지 않는다. 다못이는 모든 열쇠를 얻기 위해 다음 과정을 반복한다.

먼저 아직 잠긴 박스 중 하나를 같은 확률로 골라 폭탄으로 부수고, 그 안의 열쇠를 얻는다. 얻은 열쇠로 열 수 있는 잠긴 박스가 있으면 그 박스를 열고, 그 안의 열쇠도 얻는다. 새로 얻은 열쇠로 또 다른 잠긴 박스를 열 수 있으면 같은 일을 계속한다. 더 이상 열 수 있는 박스가 없으면 과정이 멈춘다.

아직 폭탄이 남아 있고 잠긴 박스가 남아 있다면, 같은 과정을 다시 시작한다. 다못이가 모든 열쇠를 얻을 확률을 구하시오.

첫째 줄에 박스와 열쇠의 개수 N, 폭탄의 개수 M이 공백으로 구분되어 주어진다.

N은 20 이하의 자연수이고, M은 N 이하의 자연수이다.

다못이가 모든 열쇠를 얻을 확률을 A/B 형태로 출력한다. A와 B는 서로소인 자연수이다.

N=2, M=1인 경우 1번 박스에 2번 열쇠가 들어 있다면, 1번 박스를 부순 뒤 2번 박스를 열어 모든 열쇠를 얻을 수 있다.