AT_tkppc3_e デフレゲーム

[problemUrl]: https://atcoder.jp/contests/tkppc3/tasks/tkppc3_e 配点： $ 500 $ 点 RZK 君はお金に困っている. ある日, RZK 君はお金がもらえる以下のようなゲームを見つけた. - $ 1 $ 以上 $ n $ 以下の目がすべて等確率に出る $ n $ 面体のサイコロがある. - プレイヤーは, **前に出したことのある面をもう一回出すまで**サイコロを振り続けることができる. プレイヤーは, $ a $ の目を出すと $ a $ 円もらえるが, 前に出したことのある面を出したときにはお金はもらえない. - 例えば, プレイヤーが $ 1 $ -> $ 5 $ -> $ 3 $ -> $ 5 $ という順に面を出した場合, $ 1\ +\ 5\ +\ 3\ =\ 9 $ 円プレイヤーがもらえる. RZK 君はそのゲームがすごく魅力的に見えたが参加費がとても高いので, ゲームで得られる金額の期待値を求めてから参加を検討しようと思った. そのとき, このゲームでもらえるお金の期待値を求めよ.

入力は以下の形式で標準入力から与えられる. > $ n $

このゲームでもらえるお金の期待値を出力せよ. 絶対誤差または相対誤差が $ 10^{-7} $ 未満であれば, 正解となる.

### 制約 - $ n $ は $ 1 $ 以上 $ 500\ 000 $ 以下の整数である. ### 小課題 小課題1 \[ $ 60 $点 \] - $ n\ \leq\ 8 $. 小課題2 \[ $ 120 $点 \] - $ n\ \leq\ 18 $. 小課題3 \[ $ 320 $点 \] - 追加の制約はない.