题目描述

恭弥有若干个彩球，颜色共有 $k$ 种，颜色编号为 $1,2,\ldots,k$。第 $i$ 种颜色有 $c_i$ 个球，同色球之间无法区分。

他会从袋子里依次取出所有球。取完之后，他发现对每个 $1\le i<k$，颜色 $i$ 的最后一个球都出现在颜色 $i+1$ 的最后一个球之前。

请计算可能的取球序列数量。

输入格式

第一行一个整数 $k$，表示颜色种数。

接下来 $k$ 行，第 $i$ 行一个整数 $c_i$，表示第 $i$ 种颜色的球数。

输出格式

输出一个整数，表示满足条件的取球序列数，对 $1000000007$ 取模。

样例

3
2
2
1

3

4
1
2
3
4

1680

说明

第一个样例中有 $2$ 个颜色 $1$ 的球、$2$ 个颜色 $2$ 的球、$1$ 个颜色 $3$ 的球。满足条件的取法有 $3$ 种：

1 2 1 2 3
1 1 2 2 3
2 1 1 2 3

数据范围

$1\le k\le1000$，$1\le c_i\le1000$，所有球的总数不超过 $1000$。