配点 : $400$ 点

問題文

頂点 $1$ から頂点 $N$ までの $N$ 頂点からなるグラフの頂点 $1$ に高橋君がいます。 今このグラフに辺は $1$ つも張られていません。 高橋君は以下の操作を繰り返します。

操作 :

1. (今高橋君がいる頂点も含めた) $N$ 個の頂点の中から $1$ つランダムに選ぶ。各頂点が選ばれる確率は全て $\frac{1}{N}$ であり、選択は操作毎に独立である。
2. 今高橋君がいる頂点と選ばれた頂点の間に無向辺を張り、選ばれた頂点に移動する。

グラフが連結になるまでに行われる操作の回数の期待値を求めてください。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

$N$

出力

答えを出力せよ。 想定解答との絶対誤差または相対誤差が $10^{-6}$ 以下であれば正解として扱われる。

2

2.00000000000

グラフが連結になるのは、操作において初めて頂点 $2$ が選ばれた時です。 各 $i$ について $i$ 回目の操作で初めて頂点 $2$ が選ばれる場合を考えると、答えは $\sum_{i = 1}^{\infty} (i \times (\frac{1}{2})^i) = 2$ となります。

3

4.50000000000