Kyoya and Colored Balls

题面翻译

一个袋子中有 $n$ 个彩球，他们用 $k$ 种不同的颜色染色。颜色被从 $1$ 到 $k$ 编号。同一种颜色的球看成是一样的。现在从袋中一个一个的拿出球来，直到拿完所有的球。对于所有颜色为 $i(1 \le i \le k-1)$ 的球，他的最后一个球总是在编号比他大的球拿完之前拿完，问这样情况有多少种，答案对 $10^9+7$ 取模。

输入单组测试数据。 第一行给出一个整数 $k(1 \le k \le 1000)$，表示球的种类。 接下来 $k$ 行，每行一个整数 $c_i$，表示第 $i$ 种颜色的球有 $c_i$ 个 $(1 \le c_i \le 1000)$。 球的总数目不超过 $1000$。

题目描述

Kyoya Ootori has a bag with $n$ colored balls that are colored with $k$ different colors. The colors are labeled from $1$ to $k$ . Balls of the same color are indistinguishable. He draws balls from the bag one by one until the bag is empty. He noticed that he drew the last ball of color $i$ before drawing the last ball of color $i+1$ for all $i$ from $1$ to $k-1$ . Now he wonders how many different ways this can happen.

输入格式

The first line of input will have one integer $k$ ( $1<=k<=1000$ ) the number of colors.

Then, $k$ lines will follow. The $i$ -th line will contain $c_{i}$ , the number of balls of the $i$ -th color ( $1<=c_{i}<=1000$ ).

The total number of balls doesn't exceed 1000.

输出格式

A single integer, the number of ways that Kyoya can draw the balls from the bag as described in the statement, modulo $1000000007$ .

样例 #1

样例输入 #1

3
2
2
1

样例输出 #1

3

样例 #2

样例输入 #2

4
1
2
3
4

样例输出 #2

1680

提示

In the first sample, we have 2 balls of color 1, 2 balls of color 2, and 1 ball of color 3. The three ways for Kyoya are:

<br></br>1 2 1 2 3<br></br>1 1 2 2 3<br></br>2 1 1 2 3<br></br>