Coloring the Balls

Alice has $n$ balls in $k$ colors. The colors are numbered 1 through $k$, and two balls of the same color cannot be told apart. All of the balls sit in one box.

Alice drew the balls out one at a time until the box was empty. Looking at the order she drew them, she noticed this property.

• For every integer $i$ with $1 \le i < k$, the last ball of color $i$ came out before the last ball of color $i+1$.

For example, $[1, 2, 1, 1, 2, 3]$ satisfies the condition. In contrast, $[1, 1, 2, 1, 3, 3]$ does not, because the last ball of color 1 came out fourth while the last ball of color 2 came out third.

You are given how many balls of each color the box held at the start. Count the drawing orders that satisfy the property above.

The first line contains the number of colors $k$. ($1 \le k \le 1000$)

Each of the next $k$ lines contains one integer $c_i$, the number of balls of color $i$. ($1 \le c_i \le 1000$)

The sum $n$ of all $c_i$ is at most 1000.

Print, on one line, the number of drawing orders that satisfy the property, modulo $1000000007$ ($10^9 + 7$).