Chocolate Wholesaler

Time limit1sMemory limit128 MB

Summary

Given n independent bars with individual surprise probabilities, find the probability that a carton has at least k surprises.

Level: Medium5 of 10
Topics: Probability, Dynamic programming
Solved: No attempts yet

Problem

A chocolate company is running a promotion: some chocolate bars hide a surprise inside, but you cannot tell from the outside whether a given bar contains one.

Fortunately, you can analyze each bar and determine the probability that it contains a surprise. Chocolates arrive at the wholesaler in cartons of $n$ bars, and you may only buy a whole carton, never a single bar.

Buying a carton pays off only if it contains at least $k$ surprises. Assuming the surprises occur independently across bars, compute the probability that a carton of $n$ chocolates contains at least $k$ surprises.

Input

The first line contains the number of test cases $d$ $(1 \le d \le 100)$ .

For each test case, the first line contains two integers $n$ and $k$ $(1 \le n \le 10000,\ 0 \le k \le n)$ . The second line contains $n$ real numbers giving the probability that each chocolate contains a surprise; every probability is given to four decimal places.

Output

For each test case, print on its own line the probability that a carton of $n$ chocolates contains at least $k$ surprises. Round the result to four decimal places.

Examples3

Example 1

Input

4
2 1
0.5000 0.2000
1 1
0.7500
4 1
0.5000 0.5000 0.5000 0.5000
5 2
0.2013 0.3043 0.4023 0.2023 0.1024

Expected output

Example 2
Input
```
1
3 0
0.1000 0.2000 0.3000
```
Expected output
```
1.0000
```
Example 3
Input
```
1
3 3
0.5000 0.4000 0.2000
```
Expected output
```
0.0400
```