问题

当高桥君把从神秘人物X那里得到的章鱼烧种植在庭院里时，章鱼烧树长了起来。高桥君给那棵树取名为“章鱼树”并精心地培养它。有一天，高桥君发现章鱼树结出了章鱼烧果实。于是，高桥君决定每天数一数章鱼树上长出的章鱼烧果实的个数，并记录下“到目前为止长出的章鱼烧果实的总数”。

从开始记录之后的第N天，高桥君不小心把章鱼烧果实掉进了记录本里，导致记录本上的一部分变脏无法辨认。高桥君想办法恢复这些记录，首先他想计算一共有多少种可能的记录。

输入

输入从标准输入中按以下格式给出。

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

• 第一行给出一个整数N表示记录的天数 $(1 \leq N \leq 2,000)$。

• 第二行给出N个整数，用空格分隔。其中第i个整数$A_i$表示，

  • 当$A_i$为-1时，表示第i天的记录变脏无法辨认。
  • 当$A_i$不为-1时，表示第i天的记录是可读的，且表示“到目前为止长出的章鱼烧果实的总数”为$A_i$个。

  注意，$A_1$和$A_N$不会是-1。

• 输入数据保证至少存在一种可能的记录。

部分得分

本题有部分测试点。

• 对于满足$N \leq 100$和$A_i \leq 100$的测试用例，如果答案正确则得50分。
• 对于满足$A_i \leq 2,000$的测试用例，如果答案正确则得80分。

输出

请输出作为N天的记录有多少种可能，输出结果除以$1,000,000,007$（一个质数）所得的余数，结果占一行。请在末尾换行。

输入示例1

3
1 -1 3

输出示例1

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$取余数。