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 ≤ *m*, *n* ≤ 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**

0.7000 0.4900 1.0000 0.0000 0.9940 0.9255 0.0000

Information

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