Bạn đang chơi một trò chơi một người với một bộ bài. Bộ bài có $N$ lá, mỗi lá được ghi một số nguyên từ $0$ đến $K$. Bạn xáo trộn bộ bài và rút một lá, lá bài này tạo thành quân bài khởi đầu trên tay bạn. Sau đó, bạn chơi trò chơi bằng cách liên tục chọn và bỏ một lá bài trên tay. Mỗi lần thực hiện như vậy, bạn rút từ trên cùng của bộ bài vào tay mình số lượng lá bài bằng với số nguyên ghi trên lá bài bạn vừa bỏ. (Nếu không còn đủ bài trong bộ bài, bạn sẽ rút tất cả số bài còn lại.) Bạn thắng nếu rút được tất cả các lá bài từ bộ bài và bạn thua nếu hết bài trên tay trong khi vẫn còn bài trong bộ bài. Với nội dung của bộ bài đã cho, và giả định rằng mọi cách xáo trộn bộ bài đều có khả năng xảy ra như nhau và bạn chơi một cách tối ưu, xác suất để bạn thắng trò chơi là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên cách nhau bởi dấu cách $N$ và $K$, trong đó $N$ ($1 \le N \le 1500$) là số lượng lá bài trong bộ bài và $K$ ($0 \le K \le 3$) là số nguyên lớn nhất được ghi trên bất kỳ lá bài nào.

Dòng thứ hai chứa $K + 1$ số nguyên cách nhau bởi dấu cách $a_i$ ($0 \le a_i \le N$), bắt đầu từ $i = 0$: số lượng lá bài trong bộ bài có ghi số nguyên $i$ trên đó. Đảm bảo rằng $a_K > 0$ và tổng của tất cả các $a_i$ là $N$.

Dữ liệu ra

In ra một số thực: xác suất bạn thắng nếu chơi tối ưu. Câu trả lời của bạn sẽ được chấp nhận nếu nó sai lệch so với đáp án của giám khảo một khoảng sai số tuyệt đối không quá $10^{-6}$.

Ví dụ

Ví dụ 1

4 2
2 0 2

Ví dụ 1

0.3333333333333333

Ví dụ 2

5 1
3 2

Ví dụ 2

0.0