有一个向一个方向无限延伸的棋盘。棋盘包含 $n$ 行和无限多列：它有第一列（最左侧），但没有最后一列。每一列恰好包含一个放有蛋糕的格子：蛋糕位于第 $i$ 行的概率为 $p_i$，且所有 $p_i$ 之和为 $1$。不同列中蛋糕的位置是相互独立的。

你控制一个机器人，它从第一列的某个格子开始。在每一步中，如果机器人位于格子 $(x, y)$（表示第 $x$ 行第 $y$ 列），机器人可以移动到 $(x, y+1)$、$(x-1, y+1)$ 或 $(x+1, y+1)$，前提是这些格子存在。每当机器人访问一个有蛋糕的格子时，该蛋糕就会被收集。

机器人希望尽可能多地收集蛋糕。给定概率 $p_i$，求机器人每一步平均能收集到的蛋糕数量。

假设事件发生的顺序如下。首先，所有蛋糕根据给定的概率放置在棋盘上。然后，棋盘的配置告知机器人。之后，机器人选择一个起始格子和一个移动计划，以最大化收集到的蛋糕的平均数量。

形式化地，考虑尺寸为 $n \times m$ 的棋盘序列，其中 $m = 1, 2, \dots$。对于每一个这样的有限棋盘，机器人接收配置并选择一条最优路径。令 $f(m)$ 为在 $n \times m$ 棋盘上收集到的蛋糕的期望平均数量。你的任务是计算极限 $$\lim_{m \to \infty} \frac{f(m)}{m}$$

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 6$)，表示行数。

下一行包含 $n$ 个实数 $p_i$ ($0 \le p_i \le 1$)，小数点后最多有一位数字：表示概率分布。

输出格式

可以证明，该问题的答案可以表示为一个分数 $\frac{P}{Q}$，其中 $P$ 和 $Q$ 为正整数。求出这样的 $P$ 和 $Q$，并输出 $(P \cdot Q^{-1}) \pmod{10^9 + 7}$ 的值。

样例

样例输入 1

2
0.5 0.5

样例输出 1

1

样例输入 2

3
0.3 0.3 0.4

样例输出 2

804545461

样例输入 3

4
0.2 0.3 0.2 0.3

样例输出 3

84928504