P12320 [蓝桥杯 2024 国研究生组] 深度优先搜索

小蓝正在学习深度优先搜索。给出一段小蓝写的代码 ```cpp 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$，两个合法的序列是 $\{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$。