問題文

N+1 個のバス停があり、0 から N の番号が付けられています。 バス停 i (0 ≤ i ≤ N-1)からはバス停 i+1 行きのバスが出ており、移動するのに t_{i+1} 分かかります。

また、正整数 k が定まっています。どのバス停 i (0 ≤ i ≤ N-1)からも、バス停 i+1 行きのバスは (時刻 0 分 〜 時刻 k-1 分のうち整数分のどこかで 1 回)、(時刻 k 分 〜 時刻 2k-1 分のうち整数分のどこかで 1 回)、(時刻 2k 分 〜 時刻 3k-1 分のうち整数分のどこかで 1 回)、... に発車します。 それぞれの時刻 mk 分〜 時刻 (m+1)k-1 分 の中では、等確率でどの整数分に発車するかが選ばれます。これは m ごと、バス停ごとに独立です。

すぬけ君は時刻 0 分にバス停 0 を出発し、N 本のバスに乗ってバス停 N まで移動しようとしています。 ただし、すぬけ君はあるバス停に到着すると同時に次のバスに乗ることができます。

バス停 N に到着するのに何分かかるか、期待値を求めてください。

制約

• 1 ≤ N ≤ 10^5
• 1 ≤ k ≤ 300
• 1 ≤ t_i ≤ 10^9
• 入力で与えられる値は全て整数

入力例 1

2 2
2
1

出力例 1

4.125000000000

• 時刻 0 分にバス停 0 からバスが発車し、時刻 2 分にバス停 1 に到着し、時刻 2 分にバス停 1 からバスが発車し、時刻 3 分にバス停 2 に到着する。これは確率 1/4 で起こります。
• 時刻 0 分にバス停 0 からバスが発車し、時刻 2 分にバス停 1 に到着し、時刻 3 分にバス停 1 からバスが発車し、時刻 4 分にバス停 2 に到着する。これは確率 1/4 で起こります。
• 時刻 1 分にバス停 0 からバスが発車し、時刻 3 分にバス停 1 に到着し、時刻 3 分にバス停 1 からバスが発車し、時刻 4 分にバス停 2 に到着する。これは確率 1/4 で起こります。
• 時刻 1 分にバス停 0 からバスが発車し、時刻 3 分にバス停 1 に到着し、時刻 4 分にバス停 1 からバスが発車し、時刻 5 分にバス停 2 に到着する。これは確率 1/8 で起こります。
• 時刻 1 分にバス停 0 からバスが発車し、時刻 3 分にバス停 1 に到着し、時刻 5 分にバス停 1 からバスが発車し、時刻 6 分にバス停 2 に到着する。これは確率 1/8 で起こります。

よって、求める期待値は、3 \times (1/4) + 4 \times (1/4) + 4 \times (1/4) + 5 \times (1/8) + 6 \times (1/8) = 33/8 です。

入力例 2

6 4
4
6
4
2
1
7

出力例 2

34.524398803711