눈 가린 님 게임

Sprague와 Grundy가 님(Nim) 게임을 하고 있다. 두 사람은 탁자 위에 $n$개의 동전 더미를 놓고 번갈아 가며 차례를 진행한다. 각 차례에 한 사람은 더미 하나를 골라 그 더미에서 원하는 만큼(1개 이상) 동전을 가져간다. 더 이상 유효한 수를 둘 수 없는 사람이 진다.

두 사람은 이 게임의 최적 전략을 금방 알아냈기 때문에 좀 더 흥미로운 방식을 원한다. 그래서 눈을 가리고 게임을 하기로 한다. 두 사람이 아는 것은, $i$번째 더미의 처음 동전 개수가 $[0, a_i]$ 범위의 정수 중에서 균등한 확률로 하나 뽑힌다는 사실뿐이다. 이 범위에 속한 각 정수가 뽑힐 확률은 모두 같으며, 각 더미는 서로 독립적으로 정해진다. 어떤 더미에 남아 있는 것보다 더 많은 동전을 가져가려고 시도한 사람은 그 즉시 패배한다. 특히 모든 더미가 확실히 비어 있다는 것을 알고 있더라도, 차례가 된 사람은 반드시 수를 두어야 하므로 패배한다. Sprague가 먼저 시작한다. 두 사람 모두 최적으로 플레이하고 서로의 수를 볼 수 있다고 할 때, Sprague가 이길 확률은 얼마인가?

첫째 줄에 더미의 개수 $n$ ($1 \le n \le 10^6$)이 주어진다. 둘째 줄에 $n$개의 양의 정수 $a_1, a_2, \ldots, a_n$이 주어진다. 이 정수들의 합은 $10^6$을 넘지 않는다.

Sprague가 이길 확률을 소수점 아래 정확히 $9$자리까지 반올림하여 한 줄에 출력한다.