Altar

Time limit1sMemory limit256 MB

Summary

Count the sequences of nonnegative column heights reachable by repeatedly raising the interior of any equal-height range by 1, matching known heights where not stolen (-1).

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Matrix, Implementation
Solved: No attempts yet

Problem

Sanggeun decides to build an altar of $N$ columns, hoping his grades will improve.

The height of each column is an integer, and initially every column has height $0$ . The altar is built by repeating the following process.

Choose one range of consecutive columns that all have the same height.
In the chosen range, increase the height of every column except the two at the ends by $1$ .

The figure below shows one example of building an altar.

Over the centuries, thieves stole some of the altar's columns. A distant descendant of Sanggeun now knows only the heights of the columns that remain, and wants to count how many altars can be built that match these heights.

Given the remaining heights, write a program that counts the number of altars consistent with them.

Input

The first line contains the number of columns $N$ . ( $1 \le N \le 10^4$ )

The second line contains $N$ integers $h_1, h_2, \dots, h_N$ separated by spaces. ( $-1 \le h_i \le 10^4$ ) $h_i$ is the height of the $i$ -th column; a value of $-1$ means that column was stolen and its height is unknown.

Output

On the first line, print the number of altars consistent with the remaining heights, modulo $10^9 + 7$ .

Examples3

Example 1
Input
```
3
-1 2 -1
```
Expected output
```
0
```
Example 2
Input
```
3
-1 -1 -1
```
Expected output
```
2
```
Example 3
Input
```
6
-1 -1 -1 2 -1 -1
```
Expected output
```
3
```