Oleg is very fond of binary sequences — sequences of zeros and ones. Most recently, he wrote another binary sequence of n elements in his notebook.
Oleg calculated the Z-function for the written sequence.
Z-function of the sequence s
1, . . . , s
n is called an array z[1..n], in which:
x z[1] = 0;
x If i > 1, then z[i] is equal to the length of the longest common prefix of the sequence s and the suffix of the sequence s starting from the i-th position. In other words, z[i] is equal to the maximum k such that s
1 = s
i , s
2 = s
i+1, . . . , sk = si+k−1.
For example, for the sequence s = h0, 0, 1, 1, 0, 0, 1i, the Z-function is the following: z = h0, 1, 0, 0, 3, 1, 0i.
Having written the sequence and its Z-function in a notebook, Oleg went to bed. While he was sleeping, his younger brother Yegor crept into the room and painted over the sequence and some Z-function values with a felt-tip pen. Waking up, Oleg wondered how many different binary sequences he could write in a notebook in the evening so that the unfilled values of the Z-function were correct.
Find the number of sequences you are looking for and output it modulo 109 + 7. Note that Oleg could have made a mistake when calculating the Z-function, in this case none of the sequences fit and the answer is 0.
Input data format
The first line of the input file contains an integer n — the length of the original binary sequence (1 ≤ n ≤ 1000). The second line of the input file contains n integers z[1], . . . , z[n], where z[i] — the value of the Z-function at position i, or −1 if the value at position i was filled in (−1 ≤ z[i] ≤ n).
Output data format
In the output file print a single number — remainder of the number of matching binary sequences divided by 109 + 7.
|
Enter |
Output |
3
0 0 1
|
2 |
4
0 0 1 0
|
0 |
3
0 3 -1
|
0 |
3
-1 -1 -1
|
8 |
Explanation
In the first example, the sequences {0, 1, 0 } and { 1, 0, 1 }.
In the second example, there is no binary sequence of length 4 with the given Z-function.
In the third example, z[2] = 3, which contradicts the definition of the Z-function, so the answer is 0.
In the fourth example, any binary sequence of length 3 is suitable.