题目描述

小蓝正在学习深度优先搜索。给出一段小蓝写的代码

void dfs(int rt, int deep, int fa) {
    a[++cnt] = deep;
    for (int i = head[rt]; i; i = e[i].next)
        if (e[i].to != fa) dfs(e[i].to, deep + 1, rt);
}

对一个有根树执行 dfs(root, 0, 0) 可以生成一个长度为树中结点个数的序列，依次表示对遍历的所有结点的深度，小蓝认为假如一个序列能够通过对一个有根树执行 dfs 得到，这个序列就是合法的。现在小蓝有一个只包含 $-1$ 和非负整数的序列，小蓝想要知道，有多少种把 $-1$ 替换成任意非负整数的方案，使得该序列合法。

输入格式

输入的第一行包含一个正整数 $n$ 表示序列长度。

第二行包含 $n$ 个非负整数或 $-1$，相邻整数之间使用一个空格分隔，表示序列中的数 $a_i$。

输出格式

输出一行包含一个整数，表示答案除以 $10^9 + 7$ 的余数。

2
1 -1

0

4
0 1 -1 1

2

提示

样例说明

对于样例 $2$，两个合法的序列是 $\{0, 1, 1, 1\}$ 和 $\{0, 1, 2, 1\}$。

评测用例规模与约定

• 对于 $30\%$ 的评测用例，保证序列中不会出现两个连续的 $-1$，即若 $a_i = -1$，则 $a_{i+1} \neq -1$。
• 对于 $50\%$ 的评测用例，$n \leq 300$；
• 对于所有评测用例，$1 \leq n \leq 1000000$，$-1 \leq a_i \leq n$。