Flipping Coins

There are $N$ coins on a table. Every coin starts heads up.

You are given $K$ integers $A_1, A_2, \dots, A_K$. In the first step you choose $A_1$ coins at random and flip them, in the second step you choose $A_2$ coins at random and flip them, and you repeat this until the $K$-th step. Each step picks one of the sets of size $A_i$ uniformly at random, independently of what the earlier steps did.

Compute the expected number of coins that are heads up after all steps are done.

The first line contains the number of coins $N$ ($1 \le N \le 1000$).

The second line contains the number of steps $K$ ($1 \le K \le 50$).

The third line contains $A_1, A_2, \dots, A_K$ ($1 \le A_i \le N$), separated by spaces.

Print, on one line, the expected number of coins that are heads up after all steps are done.

Round the value at the eleventh digit after the decimal point so that exactly 10 digits follow the decimal point. Round a half up. Pad with zeros when the value is an integer, so an expected value of $0$ prints as 0.0000000000.

Take $N = 3$ and $A = (2, 2)$. The first step flips 2 coins, which leaves 1 head and 2 tails. The second step has two possible outcomes.

• It picks the 2 tails and flips them. The probability is $1/3$ and the number of heads becomes 3.
• It picks 1 head and 1 tail and flips them. The probability is $2/3$ and the number of heads becomes 1.

The expected value is $\frac{1}{3} \times 3 + \frac{2}{3} \times 1 = \frac{5}{3}$.