Problem Description

I am an expert on commuter trains. Today, I am waiting for a train on the platform. The train I am waiting for starts here, so all the seats are empty, but there are $ N $ people in front of me in the queue, so it is uncertain whether I can get a seat or not.

The car has $ K $ seats arranged in a straight line, numbered consecutively from seat $ 1 $ to seat $ K $. You might think that knowing the number of seats and the number of people in front of me would be enough to determine if I can get a seat, but it is not that simple.

I know that people change how they choose a seat depending on their mood of the day. Specifically, there are two moods:

• "Desperate to Sit Mood": People in this mood will sit in the seat with the smallest number if there is any empty seat.
• "Sit if Convenient Mood": People in this mood will sit in the seat with the smallest number if there is any empty seat where both neighboring seats are also empty. If a neighboring seat does not exist, it can be considered empty.

In either mood, if there is no seat that meets the conditions, they will give up on sitting.

Now, let's number the people in front of me from the front of the queue as person $ 1 $, person $ 2 $, ……, person $ N $. That is, first person $ 1 $ enters the car and chooses a seat according to their mood. Then person $ 2 $ enters the car and chooses a seat according to their mood. This continues until person $ N $ enters the car and chooses a seat, and then I enter the car.

According to my estimation, person $ i $ will be in "Desperate to Sit Mood" with a probability of $ p_i $ percent and in "Sit if Convenient Mood" with a probability of $ 100 - p_i $ percent. Under this assumption, I want to calculate the expected number of empty seats when person $ N $ has finished entering the car and choosing a seat, that is, when I enter the car.

Input Format

$ N $ $ K $ $ p_1 $ $ p_2 $ : $ p_N $

• The first line contains an integer $ N $ ($ 1 ≦ N ≦ 100 $), representing the number of people in the queue, and an integer $ K $ ($ 1 ≦ K ≦ 200 $), representing the number of seats in the car.
• The next $ N $ lines each contain an integer $ p_i $ ($ 0 ≦ p_i ≦ 100 $), representing the probability that person $ i $ will be in "Desperate to Sit Mood".

Output Format

Output a single line with a real number representing the expected number of empty seats when person $ N $ has finished entering the car and choosing a seat. The answer will be considered correct if the absolute or relative error is within $ 10^{-6} $.

Sample Input and Output

Sample Input #1

3 4
100
30
60

Sample Output #1

1.28

Sample Input #2

5 7
28
31
59
61
30

Sample Output #2

2.11193

Sample Input #3

10 10
97
98
99
98
97
96
97
98
99
98

Sample Output #3

0.020237732

Notes/Hints

Partial Points

This problem has partial points.

• Correctly solving all datasets with $ N ≦ 10 $ will earn you $ 30 $ points.
• Correctly solving all datasets will earn you an additional $ 70 $ points, totaling $ 100 $ points.

Sample Explanation 1

Person $ 1 $ is always in "Desperate to Sit Mood", so we consider the moods of person $ 2 $ and $ 3 $:
- Both person $ 2 $ and $ 3 $ are in "Desperate to Sit Mood" with a probability of $0.3 \times 0.6 = 0.18$, leaving $ 1 $ empty seat.
- Person $ 2 $ is in "Desperate to Sit Mood" and person $ 3 $ is in "Sit if Convenient Mood" with a probability of $0.3 \times 0.4 = 0.12$, leaving $ 1 $ empty seat.
- Person $ 2 $ is in "Sit if Convenient Mood" and person $ 3 $ is in "Desperate to Sit Mood" with a probability of $0.7 \times 0.6 = 0.42$, leaving $ 1 $ empty seat.
- Both person $ 2 $ and $ 3 $ are in "Sit if Convenient Mood" with a probability of $0.7 \times 0.4 = 0.28$, leaving $ 2 $ empty seats.

Therefore, the expected number of empty seats is $1 \times 0.18 + 1 \times 0.12 + 1 \times 0.42 + 2 \times 0.28 = 1.28$.

见题面 Input 部分

见题面 Output 部分