Expect some short downtimes and small glitches during the first week of February.

Heads or tails P22482

Statement

Anna and Ivet toss coins. Anna will win the game after $m$ heads, and Ivet will win after $n$ tails (whichever happens first). They have $n$ coins, each with a probability $p_i$ of landing heads (and a probability $1 - p_i$ of landing tails). They start tossing the first coin. Anna, who chose the rules, decided that the same coin will be used as long as it lands heads, and that after landing tails the next coin will be used. How likely will Anna win?

Input

Input consists of several cases, each with $m$ , $n$ and the $n$ probabilities. You can suppose $1 \le m, n \le 1000$ .

Output

For every case, print the probability that Anna wins with 4 digits after the decimal point.

Public test cases

Input

1 1   0.7
2 1   0.7
9 2   0 1
9 1   0
1 3   0.9 0.7 0.8
4 3   0.9 0.7 0.8
1000 3   0.9 0.7 0.8

Output

Information

Author: Salvador Roura
Language: English
Translator: Salvador Roura
Original language: Catalan
Other languages: Catalan
Official solutions: C++
User solutions: C++