正解写挂

题目背景

题面好长，但很简单，还有那么多部分分和大样例。

题目描述

stri17393 是一个很菜的 OIer。在 7 月，他在 NOI 的考场上见到了《屠龙勇士》一题，这是一道基础的数论题。可怜的 stri17393 推了好久的式子才推出一个做法。

由于题目有多组测试数据，stri17393 打算将自己的程序分成多个程序块。每块之间，可能存在一些调用关系。通过将复杂的程序分块，能使得程序条理清晰，调试起来也更加方便。

然而，菜菜的 stri17393 花了一个多小时敲完这个题，一运行，发现自己的程序输出了错误的结果。

stri17393 在调试自己程序的错误时发现，自己的程序中有不少程序块写挂了，导致需要这些程序块运行结果的程序块跟着一起计算出了错误的答案。

stri17393 又花了快一个小时才把自己的程序调出来。然而由于在这道题上花了过多的时间，可怜的 stri17393 没有时间打另外两题的部分分，最终沮丧地走出了考场。

考试结束后的他想知道：他可能遇见的写挂状态总共有几种？

为方便起见，我们认为，两种写挂的状态不同，当且仅当存在一个程序块，在其中一种状态中给出了错误的运行结果，而在另一种状态中给出了正确的结果，与具体的错误结果无关。

为了简化这一问题，我们假设 stri17393 的每个程序块都具有以下特点：

    • 从题目的输入数据中获取需要的数据，或从至少一个其他程序块的运行结果中获取需要的数据；

    • 每个程序块的运行结果只会被最多一个其他程序块获取，即不存在两个程序块同时直接使用某一程序块的运行结果的情况；

    • 如果程序块 $i$ 的运行结果被程序块 $j$ 直接或间接利用，则程序块 $i$ 一定不需要直接或间接利用到程序块 $j$ 的运行结果；

    • 如果一个程序块写挂了，那它的运行结果一定错误；

    • 如果程序块 $i$ 的运行结果错误，而程序块 $j$ 需要利用到程序块 $i$ 的结果，则程序块 $j$ 的运行结果也一定错误。

    • 程序最终会输出错误的结果，当且仅当至少一个程序块（不包括主函数）给出了错误的运行结果。

输入格式

第一行包含一个正整数 $n$，表示 stri17393 的源程序中包含的程序块数量；

接下来一行包含 $n$ 个整数，其中第 $i$ 个整数 $a_i$ 表示第 $i$ 个程序块的输出会且仅会被第 $a_i$ 个程序直接使用；特别地，如果 $a_i = 0$，则表示第 $i$ 个程序块被主函数调用。

输出格式

输出一行一个整数，表示 stri17393 可能遇见的写挂状态的数量。由于答案可能很大，你需要将结果对 $20000904$ 取模后输出。

样例 #1

样例输入 #1

2
0 0

样例输出 #1

3

样例 #2

样例输入 #2

3
0 1 1

样例输出 #2

4

提示

样例三：

见选手目录下的 $\boldsymbol{wronganswer/wronganswer}\mathit{3}\boldsymbol{.in}$ 与 $\boldsymbol{wronganswer/wronganswer}\mathit{3}\boldsymbol{.ans}$。

这个样例和第 3 个测试点的性质相同。

样例四：

见选手目录下的 $\boldsymbol{wronganswer/wronganswer}\mathit{4}\boldsymbol{.in}$ 与 $\boldsymbol{wronganswer/wronganswer}\mathit{4}\boldsymbol{.ans}$。

这个样例和第 5 个测试点的性质相同。

样例五:

见选手目录下的 $\boldsymbol{wronganswer/wronganswer}\mathit{5}\boldsymbol{.in}$ 与 $\boldsymbol{wronganswer/wronganswer}\mathit{5}\boldsymbol{.ans}$。

这个样例和第 7 个测试点的性质相同。

样例六：

见选手目录下的 $\boldsymbol{wronganswer/wronganswer}\mathit{6}\boldsymbol{.in}$ 与 $\boldsymbol{wronganswer/wronganswer}\mathit{6}\boldsymbol{.ans}$。

这个样例和第 9 个测试点的性质相同。

样例七：

见选手目录下的 $\boldsymbol{wronganswer/wronganswer}\mathit{7}\boldsymbol{.in}$ 与 $\boldsymbol{wronganswer/wronganswer}\mathit{7}\boldsymbol{.ans}$。

这个样例和第 15 个测试点的性质相同。

样例8：

见选手目录下的 $\boldsymbol{wronganswer/wronganswer}\mathit{8}\boldsymbol{.in}$ 与 $\boldsymbol{wronganswer/wronganswer}\mathit{8}\boldsymbol{.ans}$。

这个样例和第 18 个测试点的性质相同。

样例一说明：

可能的写挂情况有：程序块 1 的运行结果错误而程序块 2 的运行结果正确；程序块 1 的运行正确而程序块 2 的运行错误；程序块 1 和程序块 2 的运行结果均错误。

【数据规模与约定】

每个测试点的数据规模及特点如下表所示。提示：数据范围的个位上的数字可以帮助判断是哪一种数据类型。

wronganswer.zip //仅仅只是测试数据

希望大神在回帖时能附上思路和code