문제

어떤 사람들은 자신이 파라오나 돌고래라고 상상하곤 한다. Luka도 그런 사람 중 하나이다.

Luka는 N개의 기둥이 일렬로 늘어선 부조(relief)를 만들었다. 각 기둥의 높이는 음이 아닌 정수이다.

처음에는 모든 기둥의 높이가 0이었다.

부조는 여러 단계에 걸쳐 만들어졌으며, 각 단계에서 Luka는 높이가 모두 같은 연속한 구간을 하나 선택한 뒤, 그 구간의 첫 번째와 마지막 기둥을 제외한 나머지 기둥들의 높이를 1 증가시켰다.

수백 년이 흐른 뒤, 몇몇 기둥이 도난당했다.

이제 Luka의 아주 먼 후손은, 남아 있는 기둥들의 높이와 일치하도록 만들 수 있는 원래 부조의 경우의 수를 구하려고 한다.

입력

첫째 줄에 기둥의 개수 N이 주어진다. (1 ≤ N ≤ 10000)

둘째 줄에 기둥의 높이 h_i 가 공백으로 구분되어 주어진다. (-1 ≤ h_i ≤ 10000)

h_i = -1 인 경우는 해당 기둥이 도난당했음을 의미한다.

출력

조건을 만족하는 가능한 원래 부조의 개수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

3
-1 2 -1

예제 출력 1

0

예제 입력 2

3
-1 -1 -1

예제 출력 2

2

예제 입력 3

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

예제 출력 3

3