To improve her IQ, ZJY has started studying probability theory. One day, she came up with the following problem: For a randomly generated rooted binary tree with $n$ nodes (where all non-isomorphic shapes appear with equal probability), what is the expected number of leaf nodes?

The pseudocode for determining whether two trees are isomorphic is as follows:

Algorithm 1: boolCheck(T1, T2)
Require: Two tree nodes T1, T2
if T1 == null || T2 == null then
    return T1 == null && T2 == null
else
    return Check(T1->leftson, T2->leftson) && Check(T1->rightson, T2->rightson)
end if

Input

Input a single positive integer $n$, representing the number of nodes in the rooted tree.

Output

Output the expected number of leaf nodes for this tree, with an error of less than $1e-9$.

Constraints

For 30% of the data, $1 \le n \le 10$. For 70% of the data, $1 \le n \le 100$. For 100% of the data, $1 \le n \le 10^9$.

Examples

Input 1

1

Output 1

1.000000000

Input 2

3

Output 2

1.200000000