定义一个序列的权值为，将相邻的相同的数字合并到一个集合之后，所有集合大小的乘积。以 $[1,1,3,3,1,2,2,2,1]$ 为例，权值就是 $2\times 2\times 1\times 3\times 1=12$。\par 如果一个序列是环形的，那么第一个元素和最后一个元素是相邻的，以上一个序列为例，如果他是环形的，那么他的权值就是 $(2+1)\times 2\times 1\times 3=18$。\par 现在你有 $n$ 种数字，第 $i$ 种有 $c_i$ 个，求所有能够生成的环形序列的权值的和。注意我们这里认为两个序列是不同的，是不考虑环形的，只要有一个位置不同就认为是不同的。\par 答案对 $10^9+7$ 取模。

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个整数，表示 $c_i$。

输出格式

一行一个整数表示答案。

样例数据

输入样例一

2
2 2

输出样例一

18

数据规模与约定

本题采用捆绑测试

对于 20 分的数据，$\sum c_i \le 8$

对于另外 20 分的数据，$n\le 10,c_i\le 2$

对于另外 20 分的数据，所以 $c_i$ 都一样

对于所有的数据，$2 \le n \le 50,1\le c_i \le 100$

时间限制：$1\text{s}$

空间限制：$512\text{MB}$