시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 180 58 32 28.070%

문제

상근이는 성적 향상을 기원하며 N열짜리 제단을 만들기로 했다.

제단의 각 열의 높이는 모두 정수이며, 가장 처음에 모든 열의 높이는 0이다. 제단은 다음과 같은 과정을 통해서 만들어진다. 먼저, 같은 높이를 가지는 연속하는 열을 선택한다. 그 다음, 선택한 첫 열과 마지막 열을 제외한 모든 열의 높이를 1만큼 올린다.

아래 그림은 제단을 쌓는 과정의 예시이다.

수백년이 흐르는 동안 많은 도둑들이 제단의 일부 열을 훔쳐갔다. 상근이의 손자의 손녀의 손자의.... 손녀는 남은 제단의 높이를 가지고, 가능한 제단의 경우의 수를 세려고 한다.

제단의 높이가 주어졌을 때, 남아있는 제단의 높이와 일치하는 제단의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 제단의 열의 수 N이 주어진다. (1 ≤ N ≤ 10,000)

다음 줄에는 공백으로 구분된 N개의 정수 hi가 주어진다. (-1 ≤ hi ≤ 10,000) hi는 i번 열의 높이를 나타내며, -1인 경우에는 도둑이 그 열을 훔쳐간 상태를 나타낸다.

출력

첫째 줄에 가능한 제단의 수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력

6
-1 -1 -1 2 -1 -1

예제 출력

3

힌트