Keys in Boxes

Time limit2sMemory limit128 MB

Summary

Given a uniformly random permutation of N keys among N locked boxes, find the exact probability that M bombs suffice to open every box, as a reduced fraction A/B.

Level: Medium7 of 10
Topics: Combinatorics, Probability, Math, Number theory
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Hint

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.

Examples5

Example 1
Input
```
2 1
```
Expected output
```
1/2
```
Example 2
Input
```
2 2
```
Expected output
```
1/1
```
Example 3
Input
```
3 1
```
Expected output
```
1/3
```
Example 4
Input
```
3 2
```
Expected output
```
5/6
```
Example 5
Input
```
4 2
```
Expected output
```
17/24
```