Expected Seconds to Reach Target in Bitwise OR Process

You start with the number 0. Every second, you randomly choose a number from the range [0, 2^n - 1] (inclusive) and perform a bitwise OR operation with your current number. The chosen number i is selected with probability (p_i) (with (0 \leq p_i \leq 1) for each i and (\sum_{i=0}^{2^n-1} p_i = 1)). The process continues until your number becomes (2^n - 1) (i.e. all n bits are ones).

Define (E[s]) as the expected number of seconds to reach the target starting from state s. Noting that when you are in state s (a bitmask) and you choose a number x, your new state becomes (s ;|; x). For states where (s) is not the target, we have the recurrence

[ E[s] = \frac{1 + \sum_{x:; s|x \neq s} p_x ; E[s ;|; x]}{1 - \sum_{x:; s|x = s} p_x} ]

Your task is to compute (E[0]), the expected number of seconds needed to reach the state (2^n - 1) starting from 0.

inputFormat

The input consists of two lines. The first line contains an integer (n) (the number of bits). The second line contains (2^n) space-separated real numbers (p_0, p_1, \ldots, p_{2^n-1}) representing the probabilities of choosing each number. It is guaranteed that (0 \leq p_i \leq 1) for all i and (\sum_{i=0}^{2^n-1} p_i = 1).

outputFormat

Output a single real number representing the expected number of seconds to obtain the value (2^n - 1) starting from 0. The answer should be printed with sufficient precision.

sample

1
0.5 0.5

2