hi

길이가 $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 ≤ N ≤ 50$)이 주어진다.

두 번째 줄에는 $N$개의 정수 $C\_1, C\_2, \cdots , C\_N$($1 ≤ C\_a ≤ 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$점이다.