[R10E]知识点学习2 - 代码源竞赛平台

时空限制

1S/512M

题目描述

有 $n$ 个知识点，编号从 $1$ 到 $n$，想学习知识点 $i$，必须先学习知识点 $p_i$，我们称 $p_i$ 是 $i$ 的前置知识点。保证 $p_i< i$，如果 $p_i=0$ 说明知识点 $i$ 可以直接学习。

定义合法的学习方案为学习完这 $n$ 个知识点的顺序，满足知识点 $p_i$ 在知识点 $i$ 前学习。

求一共有多少种合法的学习方案，对 $998244353$ 取模。

格式

输入格式

第一行包含一个整数 $n$ 表示知识点的数量。

第二行包含 $n$ 个整数 $p_i$，分别表示每个知识点的前置知识点。

输出格式

输出一个整数表示合法的学习方案的数量，对 $998244353$ 取模。

样例

样例输入 #1

4
0 1 0 2 

样例输出 #1

4

样例解释 #1

合法的学习方案有 $4$ 种：$\{1,2,3,4\}$，$\{1,2,4,3\}$，$\{1,3,2,4\}$，$\{3,1,2,4\}$。

样例输入 #2

6
0 1 0 3 1 5

样例输出 #2

45

数据规模

对于 $20\%$ 的数据， $n\leq 10$。

对于 $60\%$ 的数据， $n\leq 5000$。

另有 $10\%$ 的数据， $p_i=\lfloor\frac{i}{2}\rfloor$。

对于 $100\%$ 的数据， $1\leq n\leq 10^6$，$0\leq p_i< i$。