← 返回题目列表

AtCoder · arc023_3

C. 章鱼树

中文机器翻译题面 查看原题

問題文

当高桥在他的花园里种植他从神秘人那里收到的章鱼烧时,一棵章鱼烧树就长出来了。高桥将这棵树命名为“章鱼树”并珍惜它。有一天,高桥在一棵章鱼树上发现了一颗章鱼烧果实。因此,高桥决定每天统计一下长成章鱼烧树的章鱼烧坚果的数量,并记录到目前为止已经长成的章鱼烧坚果的总数。

自从我开始保存记录 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 后求余数。