Description

There are $N$ numbers in a row (their values represent heights). Initially, all numbers are zero. You may choose a continuous segment of numbers with the same height, and increase all of them by $1$ (except the first and last numbers of the segment). The figure below shows two operations:

Now, some numbers cannot be seen clearly, and we use $-1$ to represent them. Based on the remaining numbers, determine how many possible valid arrays there are such that the visible numbers fit exactly the operation rules above.

Input Format

The first line contains a positive integer $N$, the number of numbers.
The next line contains $N$ integers, representing the height of each number in order. A value of $-1$ means it cannot be seen clearly; you may replace it with any number that satisfies the conditions. Let the $i$-th number be $h_i$.

Output Format

Output one integer: the number of all possible valid arrays modulo $1000000007$.

3
-1 2 -1

0

3
-1 -1 -1

2

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

3

Hint

• $(1 \le N \le 10000)$.
• $(-1 \le h_i \le 10000)$.

Translated by ChatGPT 5