Blindfold Nim

Sprague and Grundy have been playing the game of Nim. They put $n$ stacks of coins on a table and move alternately. On each turn a player picks one stack and removes any positive number of coins from it. A player who cannot make a valid move loses.

They quickly worked out the optimal strategy, so now they want something more interesting: they decide to play blindfolded. All they know is that the initial number of coins in the $i$-th stack is drawn uniformly at random from the integers in $[0, a_i]$, every integer in that range being equally likely, and the stacks are drawn independently. A player loses immediately if he tries to take more coins from a stack than it currently holds. In particular, if a player is certain that every stack is empty, he must still move and therefore loses. Sprague moves first. Assuming both players play optimally and can see each other's moves, what is the probability that Sprague wins?

The first line contains an integer $n$ ($1 \le n \le 10^6$), the number of stacks. The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n$. The sum of these integers does not exceed $10^6$.

Print a single real number: the probability that Sprague wins, rounded to exactly $9$ digits after the decimal point.