Sprague 和 Grundy 一直在玩一种叫做 Nim 的游戏。他们在桌上放了 $n$ 堆硬币，游戏过程中两人轮流移动。每一轮中，玩家选择一堆硬币并从中取走任意正整数个硬币。第一个无法进行有效移动的玩家即为输家。

Sprague 和 Grundy 很快就找到了这个游戏的最佳策略，并想尝试一些更有趣的东西。他们决定蒙着眼睛玩。这意味着他们只知道初始时第 $i$ 堆硬币的数量是从区间 $[0, a_{i}]$ 中随机选取的，且选取该区间内任意整数的概率相等；各堆的大小是独立确定的。如果玩家试图从一堆硬币中取走比现有数量更多的硬币，则该玩家输掉游戏。特别地，如果玩家知道所有堆都确实为空，他仍然被迫移动并输掉游戏。Sprague 先手。假设两位玩家都采取最优策略，且在游戏过程中他们能看到对方的移动，请问 Sprague 获胜的概率是多少？

输入格式

标准输入的第一行包含一个整数 $n$ ($1 \le n \le 1\,000\,000$)，表示堆的数量。第二行包含一个由 $n$ 个正整数组成的序列 $a_{i}$。这些整数之和不超过 $1\,000\,000$。

输出格式

标准输出的第一行且仅包含一行，为一个实数，即 Sprague 赢得游戏的概率。输出的数字与正确答案的误差不得超过 $10^{-8}$。小数点后最多保留 20 位。

样例

输入 1

3
1 1 1

输出 1

0.375