Missing keys (2) P50427

Fulanito has finally returned home with his d keys. The keys are externally identical and have been mixed, so Fulanito doesn’t know which key corresponds to each of the d ‍locks. Fortunately, the door was designed in such a way that it will open if at most three of the keys are assigned to a wrong lock. Assuming that Fulanito assigns keys to locks uniformly at random (but for every lock, exactly one key), what is the probability that the door will open at the first try?

Input

Input consists of several cases, each one with a d between 1 and 20.

Output

For every case, print a reduced fraction with the probability of opening the door.