Counting Valid Bump Sequences

You are given a row of N numbers which represent heights. Initially all numbers are 0. A special operation is defined as follows: you may choose any contiguous segment of numbers that are all equal, and then increase every number in the segment except the first and the last one by 1. For example, if you apply the operation on a segment [L,R] (with R−L+1 ≥ 3) where every number equals v, then after the operation, the numbers at positions L+1, L+2, …, R−1 will become v+1 while the endpoints remain v.

After several such operations the final array is obtained. However, some of the numbers in the final array are obscured. They are given as -1 in the input. Your task is to count the number of possible final arrays that can be produced using the above operations so that for every position where the number is visible (i.e. not -1), it matches exactly the given value.

Note: It can be proved that an array can be produced by a sequence of the above operations if and only if all of the following conditions hold:

• The first and the last number are 0, i.e. \(a_0 = a_{N-1} = 0\).
• For every \(0 \le i < N\), \(a_i \ge 0\).
• For each adjacent pair, the difference is at most 1 in absolute value: \(|a_i - a_{i-1}| \le 1\) for \(1 \le i < N\).

You are given an array of length N where some positions are fixed (nonnegative integers) and some are unknown (represented as -1). Count how many arrays (final configurations) satisfying the conditions above agree with the fixed positions. Since the answer can be huge, output it modulo \(10^9+7\).

Input format: The first line contains an integer N. The second line contains N space‐separated integers where -1 represents an unknown value, and other numbers are between 0 and an appropriate bound.

Output format: Output a single integer — the number of possible final arrays modulo \(10^9+7\).

inputFormat

The input starts with an integer N (the length of the array). The next line contains N space‐separated integers. Each integer is either a nonnegative integer or -1 indicating that the number at that position is unknown. It is guaranteed that the array that is produced using the allowed bump operations must satisfy \(a_0=a_{N-1}=0\) and \(|a_i-a_{i-1}| \le 1\) for all valid indices.

outputFormat

Output a single integer — the number of valid final arrays (configurations) that agree with the given (non \(-1\)) numbers, modulo \(10^9+7\).

sample

5
0 0 1 1 0

1