Grasz w grę jednoosobową z talią kart. Talia składa się z $N$ kart, z których każda ma zapisaną liczbę całkowitą od $0$ do $K$. Tasujesz talię i dobierasz jedną kartę, która stanowi Twoją początkową rękę. Następnie grasz, wielokrotnie wybierając i odrzucając kartę ze swojej ręki. Za każdym razem, gdy to robisz, dobierasz z wierzchu talii do ręki tyle kart, ile wynosi liczba zapisana na właśnie odrzuconej karcie. (Jeśli w talii nie ma wystarczającej liczby kart, dobierasz wszystkie pozostałe). Wygrywasz, jeśli dobierzesz wszystkie karty z talii, a przegrywasz, jeśli w Twojej ręce zabraknie kart, podczas gdy w talii wciąż znajdują się karty. Znając zawartość talii oraz zakładając, że wszystkie możliwe potasowania talii są jednakowo prawdopodobne i że grasz optymalnie, jakie jest prawdopodobieństwo, że wygrasz grę?

Wejście

Pierwsza linia wejścia zawiera dwie liczby całkowite $N$ i $K$ oddzielone spacją, gdzie $N$ ($1 \le N \le 1500$) to liczba kart w talii, a $K$ ($0 \le K \le 3$) to największa liczba całkowita zapisana na którejkolwiek z kart.

Druga linia zawiera $K + 1$ liczb całkowitych $a_i$ ($0 \le a_i \le N$) oddzielonych spacjami, zaczynając od $i = 0$: liczba kart w talii z zapisaną liczbą $i$. Gwarantuje się, że $a_K > 0$ oraz że suma wszystkich $a_i$ wynosi $N$.

Wyjście

Wypisz liczbę rzeczywistą: prawdopodobieństwo wygranej przy optymalnej grze. Twoja odpowiedź zostanie zaakceptowana, jeśli różni się od rozwiązania wzorcowego o błąd bezwzględny nieprzekraczający $10^{-6}$.

Przykład

Wejście 1

4 2
2 0 2

Wyjście 1

0.3333333333333333

Wejście 2

5 1
3 2

Wyjście 2

0.0