Estás jugando un juego para un solo jugador con una baraja de cartas. La baraja tiene $N$ cartas, cada una con un número entero entre $0$ y $K$ escrito en ella. Barajas el mazo y robas una carta, la cual forma tu mano inicial. Luego, juegas el juego eligiendo y descartando repetidamente una carta de tu mano. Cada vez que lo haces, robas tantas cartas de la parte superior de la baraja hacia tu mano como el número entero escrito en la carta que acabas de descartar. (Si no quedan suficientes cartas en la baraja, las robas todas). Ganas si robas todas las cartas de la baraja y pierdes si te quedas sin cartas en la mano mientras aún quedan cartas en la baraja. Dado el contenido de la baraja, y asumiendo que todas las posibles barajadas son igualmente probables y que juegas de manera óptima, ¿cuál es la probabilidad de que ganes el juego?

Entrada

La primera línea de la entrada contiene dos enteros separados por espacios $N$ y $K$, donde $N$ ($1 \le N \le 1500$) es el número de cartas en la baraja y $K$ ($0 \le K \le 3$) es el número entero más grande escrito en cualquiera de las cartas.

La segunda línea contiene $K + 1$ enteros separados por espacios $a_i$ ($0 \le a_i \le N$), comenzando en $i = 0$: el número de cartas en la baraja con el número entero $i$ escrito en ellas. Se garantiza que $a_K > 0$ y que la suma de todos los $a_i$ es $N$.

Salida

Imprime un número real: la probabilidad de que ganes si juegas de manera óptima. Tu respuesta será aceptada si difiere de la solución del juez por un error absoluto de al menos $10^{-6}$.

Ejemplos

Entrada 1

4 2
2 0 2

Salida 1

0.3333333333333333

Entrada 2

5 1
3 2

Salida 2

0.0