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 to remove the last object wins.

By their agreement, the sizes of piles are selected randomly from the range ~[0,X]~ Each pile's size is taken from the same probability distribution.

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 and assuming that both players play optimally.

Input Specification

The first line of input contains ~2~ integers: ~N~ and ~X~. The second line contains ~X+1~ real numbers, given to ~6~ decimal places each: ~P(0),\cdots , P(X)~.

Output Specification

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}~.

Constraints

• ~1\le N \le 10^9~
• ~1\le X \le 100~

Example Input

2 2
0.5 0.25 0.25

Example Output

0.625

Explanation

The correct answer is exactly ~0.625~. The checker will also accept, for example, outputs like ~0.625000~, ~0.625001~and ~0.625000000~.