Keys in Boxes

There are N boxes numbered from 1 to N and N keys numbered from 1 to N. Key i opens box i.

Damot randomly places exactly one key in each box. Every possible key placement is equally likely. Then all boxes are locked.

Damot has M bombs. One bomb destroys one locked box, and the key inside that box is not damaged. Damot repeats the following process to collect every key.

First, choose one still-locked box uniformly at random, destroy it with a bomb, and take the key inside. If that key opens a still-locked box, open that box and take the key inside it. If the newly obtained key opens another still-locked box, continue in the same way. The process stops when no more boxes can be opened.

If there is still at least one bomb left and at least one locked box remains, the same process starts again. Compute the probability that Damot obtains every key.

The first line contains two integers N and M: the number of boxes and keys, and the number of bombs.

N is a positive integer at most 20, and M is a positive integer at most N.

Print the probability that Damot obtains every key in the form A/B. A and B must be coprime positive integers.

When N=2 and M=1, if box 1 contains key 2, Damot can destroy box 1 and then open box 2, collecting every key.