Problem O
Chair Hopping

Photo by Web Stock Review

The latest hit song Chair Hopping contains instructions for a group dance. To perform the dance, $n$ performers numbered from $1$ to $n$ and $n$ chairs numbered from $1$ to $n$ are required. Initially, performer $i$ is seated in chair $i$.

When a single hop is performed, the performer currently seated in chair $i$ moves to chair $s_i$. The values of $s_i$ are distinct, ensuring that each chair will be filled by exactly one performer after the hop is completed.

Exactly two hops have been completed and now performer $i$ is sitting in chair $t_i$. Observing that, you wonder in how many ways the values of $s_i$ can be chosen. The answer can be large. Output it modulo ${10}^9+7$.

Input

The first line of the input contains the integer $n$ ($1\le n\le {10}^5$). The second line of the input contains $n$ distinct integers $t_1,t_2,\dots t_n$ ($1\le t_i\le n$).

Output

Output the number of ways in which the values of $s_i$ can be chosen, modulo ${10}^9+7$.

2
1 2

2

5
3 4 5 1 2

1

16
7 16 11 1 8 2 4 5 10 14 3 15 12 9 13 6

92