cho.sh

Secret Santa

For a uniformly random permutation of N names, compute the probability that at least one resident draws their own name, rounded to 8 decimals; N can reach 10^12.

Easy3ProbabilityMathCombinatoricsImplementationNo attempts yetTime limit2sMemory limit512 MB

Problem

Christmas comes sooner every year. In one forgotten corner of the world the gift giving has already started, in the form of a Secret Santa syndicate.

Every resident of the small town of Haircombe writes their own name on a slip of paper and drops it into a hat. The hat is shuffled hard, and then the residents take turns pulling one slip back out of it.

The name a resident draws is the name of the fellow citizen they will send a gift to.

The worry with this scheme is that an unlucky resident draws their own name and ends up sending a gift to themselves. Every way of dealing the slips to the residents is equally likely, so the draw is a uniformly random permutation of the NN names. Compute the probability that at least one resident draws their own name.

Input

One line containing the integer NN (1≤N≤10121 \le N \le 10^{12}), the number of residents taking part in the Secret Santa.

Output

Print on one line the probability that at least one resident draws their own name, rounded to 8 digits after the decimal point. A value exactly halfway between two candidates rounds up. Print all 8 digits even when they are zeros, so a probability of exactly 0.50.5 prints as 0.50000000.