Sum of Circular Sequence Scores

Let $[h_1, h_2, \cdots, h_L]$ be a circular integer sequence of length $L$. Each $h_i$ is adjacent to $h_{i+1}$, and in particular $h_L$ is adjacent to $h_1$. The score of this circular sequence is the product of the sizes of all contiguous segments of equal numbers. For example, if $h = [1, 1, 2, 2, 1, 3, 3, 3, 1, 1]$, the score is $4 \times 2 \times 1 \times 3 = 24$.

Write a program that computes the sum of scores over all distinct circular sequences that contain only integers from 1 to $N$, where each integer $a$ appears exactly $C_a$ times. Two circular sequences $h$ and $h'$ are different if there exists an $i$ with $h_i \ne h'_i$.

The first line contains one integer $N$ ($1 \le N \le 50$).

The second line contains $N$ integers $C_1, C_2, \cdots, C_N$ ($1 \le C_a \le 100$), separated by single spaces.

Print, on the first line, the sum of scores over all distinct circular sequences in which each integer $a$ appears exactly $C_a$ times. The sum can be very large, so print it modulo $1\,000\,000\,007$.

In the first input, the following $6$ circular sequences are produced:

• $[1, 1, 2, 2]$: $4$ points
• $[1, 2, 1, 2]$: $1$ point
• $[1, 2, 2, 1]$: $4$ points
• $[2, 1, 1, 2]$: $4$ points
• $[2, 1, 2, 1]$: $1$ point
• $[2, 2, 1, 1]$: $4$ points

The total score is therefore $18$.