Problem Description

There are $ N+1 $ bus stops numbered from $ 0 $ to $ N $. From bus stop $ i $ ($0\ \leq\ i\ \leq\ N-1$), there is a bus to bus stop $ i+1 $ which takes $ t_{i+1} $ minutes to travel.

Also, a positive integer $ k $ is determined. From any bus stop $ i $ ($0\ \leq\ i\ \leq\ N-1$), the bus to bus stop $ i+1 $ departs at one of the integer minutes within (time $ 0 $ minutes to time $ k-1 $ minutes), (time $ k $ minutes to time $ 2k-1 $ minutes), (time $ 2k $ minutes to time $ 3k-1 $ minutes), ... . Within each time interval $ mk $ minutes to $ (m+1)k-1 $ minutes, the departure time is chosen uniformly at random from the integer minutes. This is independent for each $ m $ and each bus stop.

Snuke is going to depart from bus stop $ 0 $ at time $ 0 $ minutes and travel to bus stop $ N $ by taking $ N $ buses. Note that Snuke can board the next bus immediately upon arrival at a bus stop.

Calculate the expected time to arrive at bus stop $ N $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ k $ $ t_1 $ : $ t_N $

Output Format

Output the expected time to arrive at bus stop $ N $. The answer will be considered correct if the absolute or relative error is at most $ 10^{-9} $.

Sample Input and Output

Sample Input #1

2 2
2
1

Sample Output #1

4.125000000000

Sample Input #2

6 4
4
6
4
2
1
7

Sample Output #2

34.524398803711

Notes/Hints

Constraints

• $1\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ k\ \leq\ 300$
• $1\ \leq\ t_i\ \leq\ 10^9$
• All values given in the input are integers

Sample Explanation 1

• A bus departs from bus stop $ 0 $ at time $ 0 $ minutes, arrives at bus stop $ 1 $ at time $ 2 $ minutes, and departs from bus stop $ 1 $ at time $ 2 $ minutes, arriving at bus stop $ 2 $ at time $ 3 $ minutes. This happens with probability $ 1/4 $.
• A bus departs from bus stop $ 0 $ at time $ 0 $ minutes, arrives at bus stop $ 1 $ at time $ 2 $ minutes, and departs from bus stop $ 1 $ at time $ 3 $ minutes, arriving at bus stop $ 2 $ at time $ 4 $ minutes. This happens with probability $ 1/4 $.
• A bus departs from bus stop $ 0 $ at time $ 1 $ minutes, arrives at bus stop $ 1 $ at time $ 3 $ minutes, and departs from bus stop $ 1 $ at time $ 3 $ minutes, arriving at bus stop $ 2 $ at time $ 4 $ minutes. This happens with probability $ 1/4 $.
• A bus departs from bus stop $ 0 $ at time $ 1 $ minutes, arrives at bus stop $ 1 $ at time $ 3 $ minutes, and departs from bus stop $ 1 $ at time $ 4 $ minutes, arriving at bus stop $ 2 $ at time $ 5 $ minutes. This happens with probability $ 1/8 $.
• A bus departs from bus stop $ 0 $ at time $ 1 $ minutes, arrives at bus stop $ 1 $ at time $ 3 $ minutes, and departs from bus stop $ 1 $ at time $ 5 $ minutes, arriving at bus stop $ 2 $ at time $ 6 $ minutes. This happens with probability $ 1/8 $.

Therefore, the expected value is $3\ \times\ (1/4)\ +\ 4\ \times\ (1/4)\ +\ 4\ \times\ (1/4)\ +\ 5\ \times\ (1/8)\ +\ 6\ \times\ (1/8)\ =\ 33/8$.

见题面 Input 部分

见题面 Output 部分