Trò chơi Nim ngẫu nhiên

Xét trò chơi Nim với $n$ đống đồ vật. Hai người chơi luân phiên đi; mỗi lượt người chơi phải lấy ít nhất một vật và có thể lấy tùy ý số vật từ một đống. Người không còn nước đi (khi tất cả các đống đều rỗng) là người thua.

Kích thước của mỗi đống được chọn ngẫu nhiên và độc lập trong đoạn $[0,x]$ theo cùng một phân phối xác suất cho trước: xác suất một đống có đúng $i$ vật là $P(i)$.

Người chơi đi đầu tiên luôn chơi tối ưu. Hãy tính xác suất để người chơi đi trước thắng.

Nhắc lại kết quả cổ điển của trò chơi Nim: người đi trước thắng khi và chỉ khi tổng XOR (hoặc theo bit) kích thước tất cả các đống khác $0$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $x$: số đống và kích thước tối đa của một đống.
• Dòng thứ hai chứa $x+1$ số thực $P(0),P(1),\dots ,P(x)$, mỗi số có tối đa $6$ chữ số sau dấu chấm. Bảo đảm tổng tất cả $P(i)$ bằng $1$.

Dữ liệu ra

In ra một số thực là xác suất người chơi đi trước thắng. Đáp án được chấp nhận nếu sai lệch so với đáp án đúng không quá ${10}^{-6}$.

Ràng buộc

• $1\le n\le {10}^9$
• $1\le x\le 100$
• $0\le P(i)\le 1$ và ${\sum }_{i=0}^{x}P(i)=1$

Ví dụ