[AGC007C] Pushing Balls

在一条直线上有 $N$ 个球和 $N+1$ 个洞。记每个球与相邻的洞的距离为 $d_i \left( 1 \leq i \leq 2 \times N \right)$ 且 $d_{i + 1} - d_i = x$。 要将 $N$ 个球均推入洞中。当球滚过洞时，如果洞中还没有球，球将掉入洞中。否则，球将继续滚动。 每次会随机选择任一未进洞的球，并随机选择一个方向推球。 给定 $N, d_1, x$ ，求出在不发生碰撞的情况下，每个球移动距离的期望（误差小于 $10^{-9}$）。

[problemUrl]: https://atcoder.jp/contests/agc007/tasks/agc007_c $ N $ 個の球と $ N+1 $ 個の穴が一直線上に並んでいます。球には左から順に $ 1 $ から $ N $ の番号が、穴には左から順に $ 1 $ から $ N+1 $ の番号が振られています。$ i $ 番の球は $ i $ 番の穴と $ i+1 $ 番の穴の間に置かれており、隣り合う穴と球の間の距離を左から順に並べて得られる数列を $ d_i $ ($ 1\ \leq\ i\ \leq\ 2\ \times\ N $) とおきます。$ d_1 $ の値とパラメータ $ x $ が与えられており、$ d_i\ -\ d_{i-1}\ =\ x $ が任意の $ i $ ($ 2\ \leq\ i\ \leq\ 2\ \times\ N $) に対して成り立っています。 これら $ N $ 個の球を $ 1 $ 個ずつ転がし、穴に落としていくことを考えます。球が穴の上を通ると、その穴にすでに別の球が入っていなければその穴に落ちます。すでに別の球がその穴に入っていた場合は、球は落ちずにそのまま転がり続けます。（なお、この問題で考える球の転がし方において、球どうしが衝突することはありません。） 球を転がす際は、まだ転がされていない球の中から等確率で $ 1 $ つを選び、その球を左または右に等確率で転がします。これを $ N $ 回繰り返してすべての球を転がすとき、すべての球が移動する距離の総和の期待値を求めてください。 以下に $ N\ =\ 3 $, $ d_1\ =\ 1 $, $ x\ =\ 1 $ の場合の球の転がし方の例を挙げます。  1. $ 2 $ 番の球を左に転がす。球は $ 2 $ 番の穴に落ちる。球が移動する距離は $ 3 $ である。 2. $ 1 $ 番の球を右に転がす。球は $ 2 $ 番の穴の上を通り、$ 3 $ 番の穴に落ちる。球が移動する距離は $ 9 $ である。 3. $ 3 $ 番の球を右に転がす。球は $ 4 $ 番の穴に落ちる。球が移動する距離は $ 6 $ である。 この例では、球が移動する距離の総和は $ 18 $ となります。 なお、球をどのように転がしてもどの球も必ずいずれかの穴に落ち、最後に穴が一つだけ空のまま残ることになります。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ d_1 $ $ x $

答えを小数で出力せよ。絶対誤差または相対誤差のいずれかが $ 10^{-9} $ 以内でなければならない。

1 3 3

4.500000000000000

2 1 0

2.500000000000000

1000 100 100

649620280.957660079002380

### 制約 - $ 1\ \leq\ N\ \leq\ 200,000 $ - $ 1\ \leq\ d_1\ \leq\ 100 $ - $ 0\ \leq\ x\ \leq\ 100 $ - 入力値はすべて整数である。 ### Sample Explanation 1 球が $ 1 $ 個、穴が $ 2 $ 個あります。球から左の穴までの距離は $ 3 $ 、球から右の穴までの距離は $ 6 $ です。球を左に転がすか右に転がすかの $ 2 $ 通りの転がし方があり、それぞれにおいて球が移動する距離は $ 3,\ 6 $ です。したがって、答えは $ (3+6)/2\ =\ 4.5 $ となります。