시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 3 | 2 | 2 | 100.000% |
Arraylover Zigui has $n$ positive integers $c_1, c_2, \ldots, c_n$. He made every possible array that contains exactly $c_i$ copies of integer $i$ for each $i$ from $1$ to $n$. For example, when $n=3$, $c_1=4$, $c_2=3$, and $c_3=2$, he have made many arrays, one of which is the array [1,1,3,3,1,2,2,2,1]
.
Koo is a big fan of Zigui. He wants to make the same arrays as Zigui. But unlike Zigui, he loves circular things. Thus, he will make every array circular. In a circular array, the first element and the last element are adjacent.
Making an array has a certain cost. More specifically, the cost of making an array is the product of sizes of adjacent groups of equal values. For example, the array [1,1,3,3,1,2,2,2,1]
contains five adjacent groups of equal values: two 1
s, then two 3
s, then one 1
, then three 2
s, and finally, one 1
. The cost of making this array is therefore $2 \times 2 \times 1 \times 3 \times 1 = 12$.
In a circular array, if the values of the first element and the last element are equal, their groups are merged. Thus, the cost of making a circular array [1,1,3,3,1,2,2,2,1]
is $(2 + 1) \times 2 \times 1 \times 3 = 18$.
Calculate the sum of the costs of all circular arrays Koo will make. Note that, in a circular array, the index of each element is still important, just like in a regular array. So, for example, [1,2,1,2]
and [2,1,2,1]
are different circular arrays. As the total cost may be very large, calculate this sum modulo $10^9 + 7$.
The first line contains $n$, the number of distinct integers to use ($2 \leq n \leq 50$).
The second line contains $n$ positive integers $c_1, c_2, \ldots, c_n$, where $c_i$ is the number of occurrences of integer $i$ in each desired array ($1 \le c_i \le 100$).
Print the sum of costs of all of all circular arrays Koo will make, modulo $10^9 + 7$.
2 2 2
18
3 4 3 2
7830
4 4 4 4 4
818559048
5 1 2 3 4 5
342934740
6 7 8 9 10 11 12
609539975
For the first example, we can make six circular arrays. Here are the arrays and their costs:
[1,1,2,2]: 4 [1,2,1,2]: 1 [1,2,2,1]: 4
[2,1,1,2]: 4 [2,1,2,1]: 1 [2,2,1,1]: 4
The sum of all the costs is $18$.