|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|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
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
1s, then two
3s, then one
1, then three
2s, 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,
[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
3 4 3 2
4 4 4 4 4
5 1 2 3 4 5
6 7 8 9 10 11 12
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$.