동전 뒤집기

탁자 위에 동전 $N$개가 놓여 있다. 처음에는 모든 동전이 앞면을 위로 하고 있다.

정수 $K$개 $A_1, A_2, \dots, A_K$가 주어진다. 첫 번째 단계에서 동전 $A_1$개를 무작위로 골라 뒤집고, 두 번째 단계에서 동전 $A_2$개를 무작위로 골라 뒤집는다. 이 과정을 $K$번째 단계까지 반복한다. 각 단계에서 뒤집을 동전은 크기가 $A_i$인 모든 조합 중 하나를 균등한 확률로 고르며, 앞선 단계의 결과와 무관하게 고른다.

모든 단계를 마쳤을 때 앞면을 위로 하고 있는 동전 개수의 기댓값을 구하시오.

첫째 줄에 동전의 개수 $N$ ($1 \le N \le 1000$)이 주어진다.

둘째 줄에 단계의 수 $K$ ($1 \le K \le 50$)가 주어진다.

셋째 줄에 $A_1, A_2, \dots, A_K$ ($1 \le A_i \le N$)가 공백으로 구분되어 주어진다.

모든 단계를 마친 뒤 앞면을 위로 하고 있는 동전 개수의 기댓값을 한 줄에 출력한다.

소수점 아래 11번째 자리에서 반올림해 소수점 아래 자릿수가 정확히 10자리가 되도록 출력한다. 버리는 부분이 정확히 절반이면 올린다. 값이 정수라도 소수점 아래를 0으로 채워 10자리를 모두 적는다. 예를 들어 기댓값이 $0$이면 0.0000000000을 출력한다.

$N = 3$이고 $A = (2, 2)$인 경우를 보자. 첫 단계에서 동전 2개를 뒤집으면 앞면 1개와 뒷면 2개가 남는다. 두 번째 단계에서는 두 가지 상황이 가능하다.

• 뒷면 2개를 골라 뒤집는다. 확률은 $1/3$이고, 앞면은 3개가 된다.
• 앞면 1개와 뒷면 1개를 골라 뒤집는다. 확률은 $2/3$이고, 앞면은 1개가 된다.

따라서 기댓값은 $\frac{1}{3} \times 3 + \frac{2}{3} \times 1 = \frac{5}{3}$이다.