Problem D
Anthony and Cora
Anthony and Cora play a very exciting game. Initially, Anthony has $N$ points and Cora has $M$ points. The game then goes on for several rounds, during each round, either Anthony wins or Cora wins, the loser of the round loses $1$ point while nothing happens to the winner of the round. The game ends when either Anthony or Cora has no points left, and the one still left with points is the winner of the game.
Cora promises Anthony a sweet prize if he wins the game, but will cruelly humiliate Anthony if he loses. Anthony can very accurately evaluate himself and perfectly predict that his probability of winning the round $i$ is exactly $p_ i$. Now, in order to decide whether to play this game with Cora or not, he needs to know the probability of him winning the game.
Help Anthony find his probability of winning!
Input
The first line contain integers $1\leq N,M\leq 1\, 000$. $N+M-1$ lines follow, with the $i$-th line containing $0\leq p_ i\leq 1$, $p_ i$ has at most $6$ decimal digits.
Output
Output a single line containing the probability of Anthony winning this game. Your answer will be considered correct if its absolute or relative error doesn’t exceed $10^{-6}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 1 0.500000 |
0.500000 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 2 1.000000 0.000000 1.000000 0.000000 |
1.000000 |
