Dexterina and Womandark have been arch-rivals since they’ve known each other. Since both are super-intelligent teenage girls, they’ve always been trying to solve their disputes in a peaceful and nonviolent way. After god knows how many different challenges they’ve given to one another, their score is equal and they’re both desperately trying to best the other in various games of wits. This time, Dexterina challenged Womandark to a game of Nim.
Nim is a two-player game in which players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects from a single heap. The player who can't make a turn loses. By their agreement, the sizes of piles are selected randomly from the range \[0, _x_\]. Each pile's size is taken independently from the same probability distribution that is known before the start of the game.
Womandark is coming up with a brand new and evil idea on how to thwart Dexterina’s plans, so she hasn’t got much spare time. She, however, offered you some tips on looking fabulous in exchange for helping her win in Nim. Your task is to tell her what is the probability that the first player to play wins, given the rules as above.
## Input
The first line of the input contains two integers _n_ (1 ≤ _n_ ≤ 109) and _x_ (1 ≤ _x_ ≤ 100) — the number of heaps and the maximum number of objects in a heap, respectively. The second line contains _x_ + 1 real numbers, given with up to 6 decimal places each: _P_(0), _P_(1), ... , _P_(_X_). Here, _P_(_i_) is the probability of a heap having exactly _i_ objects in start of a game. It's guaranteed that the sum of all _P_(_i_) is equal to 1.
## Output
Output a single real number, the probability that the first player wins. The answer will be judged as correct if it differs from the correct answer by at most 10 - 6.
[samples]
Dexterina 和 Womandark 自相识以来一直是死对头。由于两人都是超级聪明的少女，她们一直以和平且非暴力的方式解决争端。在经历了无数种不同的挑战后，她们的得分持平，现在都迫切希望在各种智力游戏中击败对方。这一次，Dexterina 向 Womandark 发起了一个 Nim 游戏的挑战。
Nim 是一个两人游戏，玩家轮流从不同的堆中移除物品。每回合，玩家必须至少移除一个物品，并且只能从一个堆中移除任意数量的物品。无法进行移动的玩家输掉游戏。根据她们的约定，堆的大小从范围 #cf_span[[0, x]] 中随机选取，每个堆的大小独立地从游戏开始前已知的同一概率分布中抽取。
Womandark 正在构思一个全新的、邪恶的主意来挫败 Dexterina 的计划，因此她没有太多空闲时间。但她答应给你一些关于如何看起来更时髦的建议，以换取你帮助她赢得 Nim 游戏。你的任务是告诉她，在上述规则下，先手玩家获胜的概率是多少。
输入的第一行包含两个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 109]) 和 #cf_span[x] (#cf_span[1 ≤ x ≤ 100]) —— 分别表示堆的数量和每个堆中物品的最大数量。第二行包含 #cf_span[x + 1] 个实数，每个数最多保留 #cf_span[6] 位小数：#cf_span[P(0), P(1), ... , P(X)]。其中，#cf_span[P(i)] 表示在游戏开始时一个堆恰好有 #cf_span[i] 个物品的概率。保证所有 #cf_span[P(i)] 的和等于 #cf_span[1]。
输出一个实数，表示先手玩家获胜的概率。若你的答案与正确答案的误差不超过 #cf_span[10 - 6]，则会被判定为正确。
## Input
输入的第一行包含两个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 109]) 和 #cf_span[x] (#cf_span[1 ≤ x ≤ 100]) —— 分别表示堆的数量和每个堆中物品的最大数量。第二行包含 #cf_span[x + 1] 个实数，每个数最多保留 #cf_span[6] 位小数：#cf_span[P(0), P(1), ... , P(X)]。其中，#cf_span[P(i)] 表示在游戏开始时一个堆恰好有 #cf_span[i] 个物品的概率。保证所有 #cf_span[P(i)] 的和等于 #cf_span[1]。
## Output
输出一个实数，表示先手玩家获胜的概率。若你的答案与正确答案的误差不超过 #cf_span[10 - 6]，则会被判定为正确。
[samples]
Let $ n \in \mathbb{N} $, $ x \in \mathbb{N} $, with $ 1 \leq n \leq 10^9 $, $ 1 \leq x \leq 100 $.
Let $ P = (P(0), P(1), \dots, P(x)) $ be a probability distribution over $ \{0, 1, \dots, x\} $, where $ P(i) \geq 0 $ and $ \sum_{i=0}^x P(i) = 1 $.
Let $ S_1, S_2, \dots, S_n $ be independent random variables, each distributed according to $ P $, representing the sizes of $ n $ heaps in a game of Nim.
Define the **Nim-sum** (XOR-sum) of the heap sizes:
$$
G = S_1 \oplus S_2 \oplus \cdots \oplus S_n
$$
The first player wins if and only if $ G \neq 0 $.
Let $ \mathcal{P}_n(g) $ denote the probability that the Nim-sum of $ n $ independent heap sizes (each drawn from $ P $) equals $ g \in \mathbb{N}_0 $.
We are to compute:
$$
\mathbb{P}(\text{first player wins}) = \sum_{g=1}^{x_n} \mathcal{P}_n(g)
$$
where $ x_n $ is the maximum possible Nim-sum (bounded by $ \leq x $, since XOR of numbers in $ [0, x] $ cannot exceed the smallest power of two greater than $ x $, but since $ x \leq 100 $, we may bound the state space to $ [0, 127] $).
Since $ n $ is large ($ \leq 10^9 $) and $ x \leq 100 $, we use **fast Fourier transform over the group $ \mathbb{Z}_2^k $** (i.e., XOR convolution) with **matrix exponentiation** in the space of probability vectors over $ \{0, 1, \dots, M\} $, where $ M = 2^{\lceil \log_2(x+1) \rceil} - 1 \leq 127 $.
Let $ \mathbf{v} \in \mathbb{R}^{M+1} $ be the initial probability vector:
$$
\mathbf{v}[g] = P(g) \quad \text{for } g = 0, 1, \dots, x; \quad \mathbf{v}[g] = 0 \text{ for } g > x
$$
Define the XOR convolution operation: for two vectors $ \mathbf{a}, \mathbf{b} \in \mathbb{R}^{M+1} $,
$$
(\mathbf{a} * \mathbf{b})[g] = \sum_{i \oplus j = g} \mathbf{a}[i] \cdot \mathbf{b}[j]
$$
Then $ \mathcal{P}_n = \mathbf{v}^{*n} $, the $ n $-fold XOR convolution of $ \mathbf{v} $ with itself.
We compute $ \mathbf{v}^{*n} $ using **fast Walsh-Hadamard transform (FWHT)**:
1. Compute $ \hat{\mathbf{v}} = \text{FWHT}(\mathbf{v}) $
2. Compute $ \hat{\mathbf{v}}^n $ pointwise: $ \hat{\mathbf{v}}^n[g] = (\hat{\mathbf{v}}[g])^n $
3. Compute $ \mathcal{P}_n = \text{FWHT}^{-1}(\hat{\mathbf{v}}^n) $
Then:
$$
\boxed{\mathbb{P}(\text{first player wins}) = 1 - \mathcal{P}_n(0)}
$$