Problem A
Random Permutation
An integer sequence with length $n$, denoted by $a_1,a_2,\cdots ,a_n$, is generated randomly, and the probability of being $1,2,\cdots ,n$ are all $\frac{1}{n}$ for each $a_i$ $(i=1,2,\cdots ,n)$.
Your task is to calculate the expected number of permutations $p_1,p_2,\cdots ,p_n$ from $1$ to $n$ such that $p_i \le a_i$ holds for each $i=1,2,\cdots ,n$.
Input
The only line contains an integer $n$ $(1 \leq n \leq 50)$.
Output
Output the expected number of permutations satisfying the condition. Your answer is acceptable if its absolute or relative error does not exceed $10^{-9}$.
Formally speaking, suppose that your output is $x$ and the jury’s answer is $y$. Your output is accepted if and only if $\frac{|x - y|}{\max (1, |y|)} \leq 10^{-9}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 |
1.000000000000 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 |
1.333333333333 |
| Sample Input 3 | Sample Output 3 |
|---|---|
50 |
104147662762941310907813025277584020848013430.758061352192 |