AT_relay2018_f.バス旅行

有 $N+1$ 个公交车站，编号从 $0$ 到 $N$。从车站 $i$（其中 $0 \le i \le N-1$）有一班开往车站 $i+1$ 的公交车，行程需要 $t_{i+1}$ 分钟。

此外，给定一个正整数 $k$。对于每一个车站 $i$（$0 \le i \le N-1$），每隔一个时间段，公交车在特定时间内发车。具体来说，在 $0$ 分到 $k-1$ 分之间会随即选择某个整数时间发车一次，接着在 $k$ 到 $2k-1$ 分之间再发车一次，以此类推。每个时间段内，选择发车的分钟数是等概率随机的，并且对于每个车站来说是独立的。

Snuke 同学在时刻 $0$ 分从车站 $0$ 出发，并依次搭乘公交，目标是到达车站 $N$。他可以在到达一个站点的瞬间立刻上下一班车。

请计算 Snuke 同学到达车站 $N$ 所需时间的期望值。

输入通过标准输入，格式如下：

$N\ k\ t_1\ t_2\ \ldots\ t_N$

输出 Snuke 同学到达车站 $N$ 消耗时间的期望值。要求绝对误差或相对误差不超过 $10^{-9}$。

• $1 \le N \le 10^5$
• $1 \le k \le 300$
• $1 \le t_i \le 10^9$
• 所有输入值均为整数

样例解释

• 在时刻 $0$ 分，从车站 $0$ 发车，时刻 $2$ 分到达车站 $1$，并立刻在时刻 $2$ 分从车站 $1$ 发车，时刻 $3$ 分到达车站 $2$。这种情况发生的概率为 $1/4$。
• 同样在时刻 $0$ 分发车，时刻 $2$ 分到达车站 $1$，但在时刻 $3$ 分才从车站 $1$ 发车，时刻 $4$ 分到达车站 $2$。这种情况发生的概率也为 $1/4$。
• 还有可能在时刻 $1$ 分发车，时刻 $3$ 分到达车站 $1$，并立即继续，在时刻 $3$ 分从车站 $1$ 发车，时刻 $4$ 分到达车站 $2$，这种情况的概率为 $1/4$。
• 另一种情况是，在时刻 $1$ 分发车，时刻 $3$ 分到达车站 $1$，但要等待到时刻 $4$ 分才能从车站 $1$ 发车，到时刻 $5$ 分时到达车站 $2$，这种情况的概率为 $1/8$。
• 再有可能时刻 $1$ 分发车，时刻 $3$ 分到达车站 $1$，但再等到时刻 $5$ 分更晚发车，然后在时刻 $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$。

本翻译由 AI 自动生成