题目描述

为了提高智商，ZJY 开始学习概率论。有一天，她想到了这样一个问题：对于一棵随机生成的 $n$ 个结点的有根二叉树（所有互相不同构的形态等概率出现），它的叶子节点数的期望是多少呢？

判断两棵树是否同构的伪代码如下：

$$\begin{array}{ll} \textbf{算法 1}&\text{Check}(T1,T2) \\ 1&\textbf{Require: }\text{ 两棵树的节点}T1,T2\\ 2&\qquad\textbf{if}\ \ T1==\text{null}\textbf{ || }T2==\text{null}\textbf{ then }\\ 3&\qquad\qquad\textbf{return}\ \ T1==\text{null}\textbf{ \&\& }T2==\text{null}\\ 4&\qquad\textbf{else}\\ 5&\qquad\qquad\textbf{return}\ \text{Check}(T1->leftson,T2->leftson) \\ & \qquad\qquad\qquad \textbf{ \&\& }\text{Check}(T1->rightson,T2->rightson)\\ 6&\qquad\textbf{endif}\\ \end{array}$$

输入格式

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

输出格式

输出这棵树期望的叶子节点数，要求误差小于 $10^{-9}$。

样例 #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^9$。

source:

## 题目描述

为了提高智商，ZJY 开始学习概率论。有一天，她想到了这样一个问题：对于一棵随机生成的 $n$ 个结点的有根二叉树（所有互相不同构的形态等概率出现），它的叶子节点数的期望是多少呢？

判断两棵树是否同构的伪代码如下：


$$
\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{ || }T2==\text{null}\textbf{ then }\\
3&\qquad\qquad\textbf{return}\ \ T1==\text{null}\textbf{ \&\& }T2==\text{null}\\
4&\qquad\textbf{else}\\
5&\qquad\qquad\textbf{return}\ \text{Check}(T1->leftson,T2->leftson) \\ 
& \qquad\qquad\qquad \textbf{ \&\& }\text{Check}(T1->rightson,T2->rightson)\\
6&\qquad\textbf{endif}\\
% \hline
\end{array} 
$$

## 输入格式

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

## 输出格式

输出这棵树期望的叶子节点数，要求误差小于 $10^{-9}$。

## 样例 #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^9$。