Vous jouez à un jeu solo avec un paquet de cartes. Le paquet contient $N$ cartes, chacune portant un entier compris entre $0$ et $K$. Vous mélangez le paquet et tirez une carte, ce qui constitue votre main de départ. Vous jouez ensuite au jeu en choisissant et en défaussant de manière répétée une carte de votre main. Chaque fois que vous le faites, vous tirez autant de cartes du sommet du paquet dans votre main que l'entier inscrit sur la carte que vous venez de défausser. (S'il ne reste pas assez de cartes dans le paquet, vous les tirez toutes.) Vous gagnez si vous tirez toutes les cartes du paquet et vous perdez si vous n'avez plus de cartes en main alors qu'il reste encore des cartes dans le paquet. Étant donné le contenu du paquet, et en supposant que tous les mélanges possibles du paquet sont équiprobables et que vous jouez de manière optimale, quelle est la probabilité que vous gagniez la partie ?

Entrée

La première ligne de l'entrée contient deux entiers séparés par un espace $N$ et $K$, où $N$ ($1 \le N \le 1500$) est le nombre de cartes dans le paquet et $K$ ($0 \le K \le 3$) est le plus grand entier inscrit sur l'une des cartes.

La deuxième ligne contient $K + 1$ entiers séparés par un espace $a_i$ ($0 \le a_i \le N$), en commençant par $i = 0$ : le nombre de cartes dans le paquet sur lesquelles est inscrit l'entier $i$. Il est garanti que $a_K > 0$ et que la somme de tous les $a_i$ est égale à $N$.

Sortie

Affichez un nombre réel : la probabilité que vous gagniez si vous jouez de manière optimale. Votre réponse sera acceptée si elle diffère de la solution du juge par une erreur absolue d'au plus $10^{-6}$.

Exemples

Entrée 1

4 2
2 0 2

Sortie 1

0.3333333333333333

Entrée 2

5 1
3 2

Sortie 2

0.0