/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君が謎の人物Xからもらったたこ焼きを庭に植えると、たこ焼きの木が生えてきました。高橋君はその木に「タコヤ木」という名前をつけて大切に育てていました。ある日、高橋君はタコヤ木にたこ焼きの実がなっているのを見つけました。そこで高橋君はタコヤ木になったたこ焼きの実の個数を毎日数え、「今までになったたこ焼きの実の個数の合計」を記録していくことにしました。
記録を付け始めてから N 日が経ったある日、高橋君がたこ焼きの実をうっかり記録帳に落としてしまい、N 日分の記録のうちの一部が汚れて読めなくなってしまいました。高橋君はこの記録をなんとか復元したいと思い、まずは何通りの記録がありうるのかを計算してみることにしました。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 ... A_N
-
1 行目には、記録の日数を表した整数 N (1 ≦ N ≦ 2,000) が与えられる。
-
2 行目には、記録に関する情報を表す N 個の整数が空白区切りで与えられる。このうち i 番目の整数 A_i (1 ≦ A_i ≦ 10^9 または A_i = -1) は、
- A_i が -1 のときは、i 日目の記録が汚れて読めなくなってしまったことを表す。
- A_i が -1 でないときは、i 日目の記録が読める状態であり、「i 日目までになったたこ焼きの実の個数の合計」が A_i 個であることを表す。
ただし、A_1 と A_N は -1 ではない。
-
入力データでは、記録として考えられるものが必ず 1 通り以上ありうることが保証されます。
部分点
この問題には部分点が設定されている。
- N ≦ 100 かつ A_i ≦ 100 を満たすテストケースすべてに正解した場合は 50 点が与えられる。
- A_i ≦ 2,000 を満たすテストケースすべてに正解した場合は 80 点が与えられる。
出力
N 日分の記録としてありうるものの個数を 1,000,000,007 (素数)で割った余りを 1 行に出力せよ。出力の末尾に改行をいれること。
入力例1
3 1 -1 3
出力例1
3
3 日分の記録としてありうるものは以下の 3 通りです。
- 1 1 3
- 1 2 3
- 1 3 3
記録しているものは「今までになったたこ焼きの実の個数の合計」であるため、ある日の記録が前の日の記録よりも少なくなることはないことに注意して下さい。
入力例2
6 2 -1 -1 9 -1 9
出力例2
36
入力例3
5 1 -1 -1 -1 1000000000
出力例3
999999972
答えは非常に大きくなることがあるため、1,000,000,007 で割ったあまりを求めることを忘れないで下さい。