该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

将近晚风快吹干整条小巷,燃尽的灯火无法再将我们点亮
---晚风

背景

$YYD$是一个十分聪明的人,她最近为了锻炼脑子现出了一道题,但她觉得有点难度于是请你帮她看看.

题目描述

$关于判断$$两棵树是否重构的伪代码如$$下所示,请你帮帮YYD计算它的叶子节点数$$的期望是多少呢$

$$\def\arraystretch{1.2} \begin{array}{ll} \hline \textbf{算法 1}&\text{Check}(T1,T2) \\ \hline 1&\textbf{Require: }\text{ 两棵树的节点}T1,T2\\ 2&\qquad\textbf{if}\ \ T1=\text{null}\textbf{ or }T2=\text{null}\textbf{ then }\\ 3&\qquad\qquad\textbf{return}\ \ T1=\text{null}\textbf{ and }T2=\text{null}\\ 4&\qquad\textbf{else}\\ 5&\qquad\qquad\textbf{if}\ T1\to\mathit{value} \neq T2\to\mathit{value}\ \textbf{then} \\ 6&\qquad\qquad\qquad\textbf{return}\ \textbf{false}\\ 7&\qquad\qquad\textbf{endif}\\ 8&\qquad\qquad\textbf{return}\ \text{Check}(T1\to\mathit{leftson},T2\to\mathit{leftson}) \\ & \qquad\qquad\qquad \textbf{ and }\text{Check}(T1\to\mathit{rightson},T2\to\mathit{rightson})\\ 9&\qquad\textbf{endif}\\ \hline \end{array}$$

输入格式

输入一个正整数 $n$，表示有根树的结点数。

输出格式

输出这棵树期望的叶子节点数。

样例 #1

样例输入 #1

1

样例输出 #1

1.000000000

样例 #2

样例输入 #2

3

样例输出 #2

1.200000000

提示

数据范围

对于 $30\%$ 的数据，$1 \le n \le 10$。

对于 $70\%$ 的数据，$1 \le n \le 100$。

对于 $100\%$ 的数据，$1 \le n \le 10^{210}$。