19292번 - Circular Arrangement 출처다국어

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 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, [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$.

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$.