Description

小A正在搭积木。有N个位置可以让小A使用，初始高度都为0。小A每次搭积木的时候，都会选定一个拥有相同高度的区间[A..B]，然后将位置[A+1..B-1]上的所有积木的高度加一。不幸的是，小A把积木搭好之后没多久，小A调皮的弟弟就将其中若干个位置上的积木弄倒了。小A想知道他原来的积木是如何摆放的，所以他求助于你，请你告诉他原来有多少种可能的摆法。

Input

第一行为一个正整数N，表示小A有N个位置。

第二行有N个由空格分隔的整数Hi，表示第i个位置的积木高度。-1表示这个位置上的积木已经被弄倒了。

Output

唯一的一行，输出包括可能的摆法mod 1,000,000,007的结果。

Sample Input

输入1：

3

-1 2 -1

输入2：

3

-1 -1 -1

输入3：

6

-1 -1 -1 2 -1 -1

Sample Output

输出1：

0

输出2：

2

输出3：

3

Data Constraint

对于50%的数据 1<=N<=1000 -1<=Hi<=1000

对于80%的数据 1<=N<=10000

对于100%的数据 1<=N<=20000 -1<=Hi<=10000

---

dp水法：

设f[i,j]为第i个数，高度为j的方案数，有

f[i,j]=sum(f[i-1,j-1],f[i-1,j],f[i-1,j+1])

如果a[i]没有被破坏，那就除f[i,a[i]]外的状态都不合法。

暴力跑一边，会超一点时。把每次mod，改为统计10次取一次mod就不会超时了。

那么如果直接这样做，空间绝对会爆，因为只记录上一次那么开一个滚动数组就行了

---

代码：

const mo=1000000007;var n,i,m,j:longint;    a,k:array[0..20001]of longint;    f:array[0..1,-1..20001]of int64;begin  assign(input,'brick.in');  assign(output,'brick.out');  reset(input);  rewrite(output);  readln(n);  for i:=1 to n do read(a[i]);  if (a[i]>0) then    begin      writeln(0);      close(input);      close(output);      halt;     end;  m:=n div 2+1;  for i:=1 to n do if i