UOJ Logo

NOI.AC

1S 512MB

#759. c

统计

定义一个序列的权值为,将相邻的相同的数字合并到一个集合之后,所有集合大小的乘积。以 $[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}$