CF717D Dexterina's Lab

Dexterina 和 Womandark 从认识开始就是死对头。因为她们都是超级聪明的少女，她们总是试图用和平和非暴力的方式解决争端。他们给对方带来了很多挑战，他们的分数相等，他们都想在各种游戏中打败对方。这一次，Dexterina 挑战 Womadark 来玩 一个叫做 nim 的游戏。 nim 是一个双人游戏，玩家轮流从不同堆中拿走东西。在每一回合中，玩家必须拿走至少一个东西。不能转身的玩家就输了。根据他们的协议，桩的大小是随机选择范围 $[0, x]$。每一堆的大小都是从游戏开始前已知的同一个概率分布中独立取得的。 Womandark 想出了一个全新的主意来阻挠 Dexterina 的计划，所以她没有太多的空余时间。她给了你一些关于如何打扮得漂漂亮亮的建议，作为交换，你要帮助她在 nim 游戏中取胜。你的任务是告诉她，根据上面的规则，第一个玩家获胜的概率是多少。

输入的第一行包含两个整数 $n (1\le n\le 10^9)$ 和 $x (1\le x\le 100)$，分别表示这堆东西的个数和堆中的最大个数。第二行包含 $x+1$ 个实数，每个实数最多有 $6$ 位小数，表示 $p(0), p(1), \dots, p(x)$。这里 $p(i)$ 是指这个堆在游戏开始时拥有 $i$ 对象的概率。保证所有 $p(i)$ 的和等于 $1$。

输出一个实数，表示第一个玩家获胜的概率。如果答案与正确答案相差 $10^{-6}$ 以内，则被判定为正确。