Kostka 想要为自己构建一个大正多边形。他订购了 $n$ 条随机线段。第 $i$ 条线段的长度是一个从区间 $(0, 2^{a_i})$ 上的均匀分布中抽取的随机实数。各线段的长度是独立抽取的。Kostka 对能够用这些线段构成一个非退化的 $n$ 边形的概率很感兴趣。请帮他计算这个概率。

可以证明，在给定的约束条件下，结果可以表示为一个有理数 $\frac{\ell}{m}$，且分母 $m$ 不能被 $10^9 + 7$ 整除。对于给定的参数 $a_i$，你的程序应该输出该分数除以 $10^9 + 7$ 的余数，即一个满足 $m \cdot x \equiv \ell \pmod{10^9 + 7}$ 的整数 $x$。

注意：请记住，线段的长度不是从区间 $(0, a_i)$ 中抽取的，而是从 $(0, 2^{a_i})$ 中抽取的。

输入格式

第一行包含一个正整数 $n$ ($3 \le n \le 1000$)，表示有序线段的数量。第二行包含一个由 $n$ 个整数 $a_1, \dots, a_n$ ($0 \le a_i \le 50$) 组成的序列，表示用于抽取各线段长度的参数。

输出格式

输出一个整数，即能够用 Kostka 订购的随机线段构成一个非退化 $n$ 边形的概率除以 $10^9 + 7$ 的余数。

样例

输入 1

3
0 2 0

输出 1

166666668

说明

所求概率恰好为 $\frac{1}{6}$。