問題文
当高桥在他的花园里种植他从神秘人那里收到的章鱼烧时,一棵章鱼烧树就长出来了。高桥将这棵树命名为“章鱼树”并珍惜它。有一天,高桥在一棵章鱼树上发现了一颗章鱼烧果实。因此,高桥决定每天统计一下长成章鱼烧树的章鱼烧坚果的数量,并记录到目前为止已经长成的章鱼烧坚果的总数。
自从我开始保存记录 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 后求余数。