Matcom Online Grader

Una secuencia de divisores aleatoria, o $\text{SDA}$, es una secuencia de enteros positivos  $\{a_1, a_2, ..., a_k = 1\}$ que satisface las siguientes condiciones:

1- $a_1$ es un entero positivo.
2- $a_{m+1}$ es un divisor positivo de $a_m$ escogido de forma aleatoria para todo $m$ con $a_m \ne 1$.
3- Si para algún entero positivo $k$ se cumple que $a_k = 1$, entonces la $\text{SDA}$ termina en $k$ (no habrá otro término después de $a_k$).

Algunas $\text{SDA}$ válidas son $\{1\}$, $\{125,5,5,1\}$, y $\{24,24,6,2,1\}$. Note que algunas $\text{SDA}$ son más probables que otras. Por ejemplo, considere las $\text{SDA}$ que comienzan con $2$. El siguiente término siguiendo a $2$ tiene una probabilidad $\frac{1}{2}$ de ser $2$ y $\frac{1}{2}$ de ser $1$. Como las $\text{SDA}$ terminan en $1$, la secuencia $\{2,1\}$ tiene probabilidad $\frac{1}{2}$ de ocurrir, mientras que $\{2,2,2,2,2,2,2,1\}$ tiene una probabilidad de $\frac{1}{2^7}$=$\frac{1}{128}$ de ocurrir. Luego, de todas las $\text{SDA}$ comenzando con $2$, $\{2,1\}$ es más probable que ocurra que $\{2,2,2,2,2,2,2,1\}$. Para este problema queremos determinar el valor esperado de la longitud de la $\text{SDA}$ comenzando con $n$ (la secuencia $\{125,5,5,1\}$ tiene longitud $4$).

Input

Línea 1 : Un entero $N$ $(1 \le N \le 10^{15})$.

Output

Línea 1 : El valor esperado de la $\text{SDA}$ comenzando por $N$. Para la respuesta es aceptado un error relativo o absoluto de $10^{−6}$.

Sample test(s)

Hints

Hint

El valor esperado lo definimos como : $\displaystyle\sum_{x \in S}{|x| * p(x)}$ , donde $S$ es el conjunto de las $\text{SDA}$ comenzando en $n$, $|x|$ es la longitud de la $\text{SDA}$ $x$ y $p(x)$ es la probabilidad de que $x$ ocurra. Por ejemplo, si $n=2$, entonces $S=\{\{2,1\},\{2,2,1\},\{2,2,2,1\},\{2,2,2,2,1\}…\}$, luego, el valor esperado de la longitud de la $\text{SDA}$ comenzando con $2$ es: $|\{2,1\}|*p(\{2,1\})+|\{2,2,1\}|*p(\{2,2,1\})+|\{2,2,2,1\}|*p(\{2,2,2,1\})+... =2*\frac{1}{2}+3*\frac{1}{4}+4*\frac{1}{8}+... =3$