Вы играете в одиночную игру с колодой карт. В колоде $N$ карт, на каждой из которых написано целое число от $0$ до $K$. Вы перемешиваете колоду и берете одну карту, которая становится вашей начальной рукой. Затем вы играете в игру, многократно выбирая и сбрасывая карту из своей руки. Каждый раз, когда вы это делаете, вы берете из колоды в руку столько карт, сколько написано на только что сброшенной вами карте. (Если в колоде осталось недостаточно карт, вы берете их все.) Вы выигрываете, если вытянули все карты из колоды, и проигрываете, если у вас закончились карты в руке, в то время как в колоде еще остались карты. Учитывая содержимое колоды, а также предполагая, что все возможные перетасовки колоды равновероятны и вы играете оптимально, какова вероятность того, что вы выиграете игру?

Входные данные

Первая строка входных данных содержит два целых числа $N$ и $K$, разделенных пробелом, где $N$ ($1 \le N \le 1500$) — количество карт в колоде, а $K$ ($0 \le K \le 3$) — наибольшее целое число, написанное на любой из карт.

Вторая строка содержит $K + 1$ целое число $a_i$ ($0 \le a_i \le N$), разделенных пробелом, начиная с $i = 0$: количество карт в колоде, на которых написано число $i$. Гарантируется, что $a_K > 0$ и что сумма всех $a_i$ равна $N$.

Выходные данные

Выведите вещественное число: вероятность того, что вы выиграете, если будете играть оптимально. Ваш ответ будет принят, если он отличается от ответа жюри не более чем на $10^{-6}$ по абсолютной величине.

Примеры

Пример 1

4 2
2 0 2

0.3333333333333333

Пример 2

5 1
3 2

0.0