Arraylover Zigui 拥有 $n$ 个正整数 $c_1, c_2, \dots, c_n$。他构造了所有可能的数组，使得每个数组中整数 $i$ 恰好出现 $c_i$ 次（对于每个 $1 \le i \le n$）。例如，当 $n = 3, c_1 = 4, c_2 = 3, c_3 = 2$ 时，他构造了许多数组，其中之一是 $[1, 1, 3, 3, 1, 2, 2, 2, 1]$。

Koo 是 Zigui 的忠实粉丝。他想要构造和 Zigui 一样的数组，但与 Zigui 不同的是，他喜欢循环结构。因此，他将构造循环数组。在循环数组中，第一个元素和最后一个元素是相邻的。

构造一个数组有一定的代价。具体来说，构造一个数组的代价是相邻相等元素组大小的乘积。例如，数组 $[1, 1, 3, 3, 1, 2, 2, 2, 1]$ 包含五个相邻的相等元素组：两个 $1$，接着是两个 $3$，接着是一个 $1$，接着是三个 $2$，最后是一个 $1$。因此，构造该数组的代价为 $2 \times 2 \times 1 \times 3 \times 1 = 12$。

在循环数组中，如果第一个元素和最后一个元素的值相等，它们的组会合并。因此，构造循环数组 $[1, 1, 3, 3, 1, 2, 2, 2, 1]$ 的代价为 $(2 + 1) \times 2 \times 1 \times 3 = 18$。

计算 Koo 将要构造的所有循环数组的代价之和。注意，在循环数组中，每个元素的下标仍然很重要，就像在普通数组中一样。因此，例如 $[1, 2, 1, 2]$ 和 $[2, 1, 2, 1]$ 是不同的循环数组。由于总代价可能非常大，请计算该和对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $n$，表示要使用的不同整数的个数 ($2 \le n \le 50$)。

第二行包含 $n$ 个正整数 $c_1, c_2, \dots, c_n$，其中 $c_i$ 是每个目标数组中整数 $i$ 出现的次数 ($1 \le c_i \le 100$)。

输出格式

输出 Koo 将要构造的所有循环数组的代价之和，对 $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

说明

对于第一个样例，我们可以构造六个循环数组。以下是这些数组及其代价：

$[1, 1, 2, 2]: 4 \quad [1, 2, 1, 2]: 1 \quad [1, 2, 2, 1]: 4$ $[2, 1, 1, 2]: 4 \quad [2, 1, 2, 1]: 1 \quad [2, 2, 1, 1]: 4$

所有代价之和为 $18$。