Problem Description

Takoyaki received a takoyaki from a mysterious person X and planted it in his garden. A takoyaki tree sprouted, which Takoyaki named "Takoyaki Tree" and cherished. One day, Takoyaki found takoyaki fruits on the tree. He decided to count the number of takoyaki fruits every day and record the "total number of takoyaki fruits that have sprouted so far".

After $ N $ days since he started recording, Takoyaki accidentally dropped a takoyaki fruit on his notebook, smudging some of the $ N $ days' records and making them unreadable. Takoyaki wants to restore the records and first decided to calculate how many possible records there could be.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ ... $ A_N $

• The first line contains an integer $N\ (1\ ≦\ N\ ≦\ 2,000)$, representing the number of days recorded.

• The second line contains $ N $ integers separated by spaces, representing the information about the records. The $ i $ -th integer $A_i\ (1\ ≦\ A_i\ ≦\ 10^9\ or\ A_i\ =\ -1)$ indicates:

• When $ A_i $ is $ -1 $, it means the record for the $ i $ -th day is smudged and unreadable.

• When $ A_i $ is not $ -1 $, it means the record for the $ i $ -th day is readable and the "total number of takoyaki fruits that have sprouted by the $ i $ -th day" is $ A_i $ .

Note that $ A_1 $ and $ A_N $ are not $ -1 $.
- The input data guarantees that there is always at least one possible record.

Output Format

Output the number of possible records for $ N $ days, modulo $ 1,000,000,007 $ (a prime number). End the output with a newline.

Sample Input and Output

Sample Input #1

3
1 -1 3

Sample Output #1

3

Sample Input #2

6
2 -1 -1 9 -1 9

Sample Output #2

36

Sample Input #3

5
1 -1 -1 -1 1000000000

Sample Output #3

999999972

Notes/Hints

Partial Points

This problem has partial points:

• If you correctly solve all test cases where $N\ ≦\ 100$ and $A_i\ ≦\ 100$, you will be awarded $ 50 $ points.
• If you correctly solve all test cases where $A_i\ ≦\ 2,000$, you will be awarded $ 80 $ points.

Sample Explanation 1

The possible records for 3 days are as follows:
- 1 1 3
- 1 2 3
- 1 3 3
Note that since the records are the "total number of takoyaki fruits that have sprouted so far", a day's record cannot be less than the previous day's record.

Sample Explanation 3

The answer can be very large, so do not forget to find the remainder when divided by $ 1,000,000,007 $.

见题面 Input 部分

见题面 Output 部分