시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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$.
{"ft_lang_label":"__label__en","ft_lang_prob":0.79393774,"math_prob":0.99976534,"size":2191,"snap":"2020-24-2020-29","text_gpt3_token_len":792,"char_repetition_ratio":0.13854596,"word_repetition_ratio":0.04796163,"special_character_ratio":0.38612506,"punctuation_ratio":0.19725558,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9974066,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-07-04T09:00:59Z\",\"WARC-Record-ID\":\"<urn:uuid:addf9014-70f6-4a31-8c51-461bfc887b15>\",\"Content-Length\":\"32343\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:81d9287b-8749-49f6-8d71-9714ded3088a>\",\"WARC-Concurrent-To\":\"<urn:uuid:302eedd6-7334-441a-b462-69e792b1c3e8>\",\"WARC-IP-Address\":\"3.113.117.161\",\"WARC-Target-URI\":\"https://www.acmicpc.net/problem/19292\",\"WARC-Payload-Digest\":\"sha1:YTXD6ZH4UHE6HTNCDPFXV2TZJIMTZLJV\",\"WARC-Block-Digest\":\"sha1:IDZU26QBQV6R6AUH2RQ52RT5LCGVLIMT\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-29/CC-MAIN-2020-29_segments_1593655886095.7_warc_CC-MAIN-20200704073244-20200704103244-00092.warc.gz\"}"}