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\le n\le 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|)}\le {10}^{-9}$.

2

1.000000000000

3

1.333333333333

50

104147662762941310907813025277584020848013430.758061352192