[TJOI2015]概率论

题目描述

为了提高智商,ZJY 开始学习概率论。有一天,她想到了这样一个问题:对于一棵随机生成的 $n$ 个结点的有根二叉树(所有互相不同构的形态等概率出现),它的叶子节点数的期望是多少呢? 判断两棵树是否同构的伪代码如下: ![](https://cdn.luogu.com.cn/upload/pic/10996.png)

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

1

输出样例 #1

1.000000000

输入样例 #2

3

输出样例 #2

1.200000000

说明

## 数据范围 对于 $30\%$ 的数据,$1 \le n \le 10$。 对于 $70\%$ 的数据,$1 \le n \le 100$。 对于 $100\%$ 的数据,$1 \le n \le 10^9$。