시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 2 1 1 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 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$.

예제 입력 1

2
2 2

예제 출력 1

18

예제 입력 2

3
4 3 2

예제 출력 2

7830

예제 입력 3

4
4 4 4 4

예제 출력 3

818559048

예제 입력 4

5
1 2 3 4 5

예제 출력 4

342934740

예제 입력 5

6
7 8 9 10 11 12

예제 출력 5

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