Problem Description

HKE has recently written a function $\text{rand}(l,r)$, where $l$ and $r$ are positive integers and $l \le r$. This function returns any positive integer in the interval $[l,r]$ with equal probability. He then wrote another function:

int work(int x){
    if(x==1) return 0;
    else return work(rand(1,x))+1;
}

This code in Pascal would look like:

function work(x:integer):integer;
begin
    if x=1 then exit(0);
    else exit(work(rand(1,x))+1);
end;

Given a positive integer $n$, what is the expected value of the return value of $\text{work}(n)$?

The definition of expectation: Suppose all possible return values of $\text{work}(n)$ are $x_1, x_2, \dots, x_k$, with probabilities $p_1, p_2, \dots, p_k$, then the expectation is:

$$\mathbb{E}=\sum_{i=1}^{k}x_i p_i$$

Input Format

A single positive integer $n$.

Output Format

A real number representing the expected value of $\text{work}(n)$, rounded to 5 decimal places.

Sample Input and Output

Sample Input #1

2

Sample Output #1

2.00000

Sample Input #2

3

Sample Output #2

2.50000

Sample Input #3

100000

Sample Output #3

13.09014

Notes

Sample 1 Explanation:
$\text{work}(2)$ has a $1/2$ probability of returning $1$, a $1/4$ probability of returning $2$, a $1/8$ probability of returning $3$, and so on.
Thus, the expectation is $1/2 + 2/4 + 3/8 + \dots = 2$.

Data Range:
For $30\%$ of the data, $n \le 9$;
For $50\%$ of the data, $n \le 1000$;
For $70\%$ of the data, $n \le 1000000$;
For $100\%$ of the data, $1 \le n < 2^{31}$.

见题面 Input 部分

见题面 Output 部分