图连通的期望步数

题目描述

有一个由顶点 $1$ 到顶点 $N$ 共 $N$ 个顶点组成的图,高桥君在顶点 $1$。

现在这个图还没有连任何边。

高桥君反复进行以下操作。

操作:

• 从(包括高桥君当前所在顶点的)$N$ 个顶点中随机选择 $1$ 个。每个顶点被选中的概率都是 $\frac{1}{N}$,且每次选择相互独立。
• 在高桥君当前所在的顶点与选中的顶点之间连一条无向边,并移动到选中的顶点。

求到图连通为止所进行操作次数的期望值。

输入格式

输入按以下格式从标准输入给出:

$N$

输出格式

输出答案。

与期望答案的绝对误差或相对误差不超过 $10^{-6}$ 即判为正确。

样例

2

2.00000000000

图是在操作中第一次选中顶点 $2$ 时连通的。

对每个 $i$,考虑第 $i$ 次操作时首次选中顶点 $2$ 的情况,答案为 $\sum_{i = 1}^{\infty} (i \times (\frac{1}{2})^i) = 2$。

3

4.50000000000

数据范围

• $2 \le N \le 10^5$