공 색칠하기

Alice는 색이 $k$종류인 공 $n$개를 가지고 있다. 색에는 1번부터 $k$번까지 번호가 붙어 있고, 색이 같은 공끼리는 구별할 수 없다. 공은 모두 상자 하나에 담겨 있다.

Alice는 상자가 빌 때까지 공을 하나씩 꺼냈다. 꺼낸 순서를 살펴보니 다음 성질이 성립했다.

• 1 이상 $k$ 미만의 모든 자연수 $i$에 대해, 색이 $i$인 마지막 공이 색이 $i+1$인 마지막 공보다 먼저 나왔다.

예를 들어 $[1, 2, 1, 1, 2, 3]$은 조건을 만족한다. 반면 $[1, 1, 2, 1, 3, 3]$은 색이 1인 마지막 공이 네 번째, 색이 2인 마지막 공이 세 번째에 나왔으므로 조건을 만족하지 않는다.

처음에 상자에 들어 있던 색깔별 공의 개수가 주어진다. 위 성질을 만족하는 꺼내는 순서가 몇 가지인지 세어라.

첫째 줄에 공의 색깔 종류 수 $k$가 주어진다. ($1 \le k \le 1000$)

다음 $k$개 줄에는 색이 $i$인 공의 개수 $c_i$가 한 줄에 하나씩 주어진다. ($1 \le c_i \le 1000$)

모든 $c_i$의 합 $n$은 1000을 넘지 않는다.

위 성질을 만족하도록 공을 꺼내는 순서의 가짓수를 $1000000007$($10^9 + 7$)로 나눈 나머지를 한 줄에 출력한다.