Il y a $n$ hommes et $n$ femmes qui participent à une compétition de danse. La compétition se déroule selon les règles suivantes :

1. Initialement, les hommes et les femmes sont appariés au hasard en $n$ couples, et tous les couples sont disposés en cercle.
2. Le juge lance une pièce et détermine le nombre $k$, qui est soit 1, soit 2 avec une probabilité égale. Ensuite, un autre lancer de pièce détermine soit le sens « horaire », soit le sens « anti-horaire », également avec une probabilité égale.
3. Conformément aux lancers de pièce de l'étape précédente, les femmes changent de partenaire en se déplaçant sur le cercle de $k$ positions dans la direction correspondante (tandis que les hommes restent en place).
4. Si, après le déplacement, une femme est appariée avec un homme avec qui elle a déjà dansé lors de l'un des tours précédents, la compétition s'arrête et les juges déterminent les gagnants. Sinon, les couples actuels dansent un tour, les juges les évaluent soigneusement, puis le processus retourne à l'étape 2.

Déterminez le nombre attendu de tours qui seront dansés pendant la compétition.

Entrée

Une seule ligne contenant l'entier $n$ ($2 \le n \le 50$).

Sortie

Affichez la réponse avec une précision de $10^{-9}$.

Exemples

Entrée 1

3

Sortie 1

2.50000000000000000000

Entrée 2

5

Sortie 2

3.21875000000000000000