Bobo 正在处理 $n$ 个整数 $a_1, a_2, \dots, a_n$。每次他从这些数中等概率随机选择两个整数 $x, y$，并将它们替换为 $x + y$ 或 $x \cdot y$（因此，在第一次操作后，共有 $n \cdot (n - 1)$ 种等概率的结果）。

在重复上述操作 $(n - 1)$ 次后，最终只剩下一个整数。Bobo 想知道这个剩余整数的期望值。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 2000$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)。

输出格式

如果期望值为 $\frac{P}{Q}$，请输出 $P \cdot Q^{-1} \pmod{10^9 + 7}$。 注意 $Q^{-1}$ 是 $Q$ 在模 $10^9 + 7$ 下的乘法逆元，满足 $Q \cdot Q^{-1} \equiv 1 \pmod{10^9 + 7}$。

样例

样例输入 1

2
1 1

样例输出 1

500000005

样例输入 2

3
1 2 3

样例输出 2

250000008