시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 17 11 11 73.333%

문제

Alice는 k종류의 색을 가진 n개의 공을 갖고 있다. 공의 색깔들은 각각 1~k까지 번호가 매겨져 있으며, 같은 색의 공들은 서로 구분이 불가능하다. 이 공들은 모두 하나의 상자에 들어 있는 상태이다.

Alice는 상자가 빌 때까지, 상자에서 n개의 공을 하나씩 꺼냈다. 이렇게 공을 꺼내고 나니, 꺼낸 공들의 순서가 다음과 같은 신기한 성질을 만족하는 것을 알게 되었다.

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

즉, [1,2,1,1,2,3] 등의 수열은 조건을 만족하지만, [1,1,2,1,3,3] 등의 수열은 색깔이 1인 마지막 공이 4번째, 색깔이 2인 마지막 공이 3번째에 나왔으므로 조건을 만족하지 않는다.

Alice는 이런 상황이 발생할 경우의 수가 얼마나 많은지 궁금해졌다. 처음에 상자에 들어있던 각 색깔의 공의 개수가 주어질 때, 이런 상황이 발생할 경우의 수를 출력하시오.

입력

첫 번째 줄에는 공의 색깔의 종류 k가 주어진다. (1 ≤ k ≤ 1000)

다음 k개의 줄에는 각 색깔의 공의 개수를 나타내는 자연수 ci가 주어진다. (1 ≤ ci ≤ 1000)

모든 ci의 합(n)은 1000을 넘지 않음이 보장된다.

출력

위와 같은 성질을 만족하도록 공을 뽑을 수 있는 순서의 가짓수를 1,000,000,007 (109+7)로 나눈 나머지를 출력한다. 

예제 입력 1

3
2
2
1

예제 출력 1

3

예제 입력 2

4
1
2
3
4

예제 출력 2

1680