You are playing an 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 $A$ is the prerequisite for $B$, ability $B$ is the prerequisite for $C$, but ability $C$ is also the prerequisite for $A$.

There are a total of $N$ abilities in the game, numbered from $1$ to $N$. 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 $N$ abilities. As this number can be very large, you would like it modulo ${10}^9+7$.

Constraints

Subtask 1 [10%]

$1\le N\le 8$

Subtask 2 [20%]

$1\le N\le 16$

Subtask 3 [20%]

$1\le N\le 1000$

Subtask 4 [50%]

$1\le N\le 100000$

Input Specification

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

The next line will contain $N$ space-separated integers, where the $i^{th}$ number denotes the prerequisite for the $i^{th}$ ability. If it is a basic ability (no prerequisite), this number will be $0$.

Output Specification

The number of different orders in which you can unlock all the abilities, modulo ${10}^9+7$.

Sample Input

4
0 1 1 0

Sample Output

8

Explanation for Sample Output

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