원형 정수열 점수의 총합

길이가 $L$인 원형 정수열 $[h_1, h_2, \cdots, h_L]$이 있다고 하자. $h_i$와 $h_{i+1}$은 인접해 있으며, 특별히 $h_L$과 $h_1$도 인접해 있다. 이 원형 정수열의 점수는 같은 수가 인접해 이루는 부분의 크기를 모두 구해서 곱한 값이다. 예를 들어 $h = [1, 1, 2, 2, 1, 3, 3, 3, 1, 1]$이면, 점수는 $4 \times 2 \times 1 \times 3 = 24$점이 된다.

1 이상 $N$ 이하의 정수만 포함하면서, 정수 $a$를 정확히 $C_a$개 포함하는 서로 다른 원형 정수열에 대해 점수의 총합을 구하는 프로그램을 작성하라. 두 원형 정수열 $h$와 $h'$이 다르다는 것은 $h_i \ne h'_i$인 $i$가 존재한다는 것이다.

첫 번째 줄에 하나의 정수 $N$($1 \le N \le 50$)이 주어진다.

두 번째 줄에는 $N$개의 정수 $C_1, C_2, \cdots, C_N$($1 \le C_a \le 100$)이 공백 하나로 구분되어 주어진다.

첫 번째 줄에 정수 $a$를 정확히 $C_a$개 포함하는 모든 서로 다른 원형 정수열에 대해 점수의 총합을 출력한다. 이 수는 매우 클 수 있으므로, $1\,000\,000\,007$로 나눈 나머지를 출력한다.

첫 번째 입력에서 만들어지는 원형 정수열은 다음의 $6$가지이다.

• $[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$점

그러므로 총 $18$점이다.