$n$ 人の男性と $n$ 人の女性がダンス競技に参加する。競技は以下のルールに従って行われる。

1. 最初、男性と女性はランダムに $n$ 組のカップルにペアリングされ、すべてのカップルが円状に配置される。
2. 審判がコインを投げ、$k$ を決定する。$k$ は等確率で 1 または 2 となる。その後、もう一度コインを投げ、「時計回り」または「反時計回り」の方向を決定する。これも等確率である。
3. 前のステップでのコイン投げの結果に従い、女性は円上で $k$ ポジション分、指定された方向に移動することでパートナーを入れ替える（男性はその場に留まる）。
4. 移動後、ある女性が過去のラウンドですでに踊ったことのある男性とペアになった場合、競技は終了し、審判が勝者を決定する。そうでなければ、現在のカップルが1ラウンド踊り、審判が彼らを慎重に評価した後、プロセスはステップ 2 に戻る。

競技中に行われるダンスのラウンド数の期待値を求めよ。

入力

整数 $n$ ($2 \le n \le 50$) が1行で与えられる。

出力

$10^{-9}$ の精度で答えを出力せよ。

入出力例

入力 1

3

出力 1

2.50000000000000000000

入力 2

5

出力 2

3.21875000000000000000