## DMPG '16 S4 - MMORPG II

View as PDF

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

You are playing a MMORPG where abilities are unlocked by points which you earn upon leveling up. Of course, abilities can only be learned in certain orders. For example, the one-handed sword skill must be first learned before learning the dual-wielding skill, and Vorpal Strike is a prerequisite for Starburst Stream. Abilities that have a prerequisite ability are known as advanced abilities, whereas abilities that have no requirements to unlock are called basic abilities. In this particular game, all advanced abilities have exactly one prerequisite ability. Naturally, it is guaranteed that the prerequisites are never cyclical — that is, there will never be a case where ability is the prerequisite for , ability is the prerequisite for , but ability is also the prerequisite for .

There are a total of abilities in the game, numbered from to . Since you like to be flexible with your build path, you would like to know the number of different orders in which you can unlock the abilities. As this number can be very large, you would like it modulo .

#### Input Specification

The first line of input will contain , the total number of abilities to unlock.

The next line will contain space-separated integers, where the number denotes the prerequisite for the ability. If it is a basic ability (no prerequisite), this number will be .

#### Output Specification

The number of different orders in which you can unlock all the abilities, modulo .

#### Sample Input

4
0 1 1 0

#### Sample Output

8

#### Explanation for Sample Output

There are a total of 4 abilities, where and are basic abilities and and are advanced abilities that require to be unlocked first. The 8 orders of unlocking the abilities are as follows: , , , , , , , and .