Problem G
Chair Hopping
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 \leq n \leq 10^5$). The second line of the input contains $n$ distinct integers $t_1, t_2, \dots t_ n$ ($1 \leq t_ i \leq n$).
Output
Output the number of ways in which the values of $s_ i$ can be chosen, modulo $10^9 + 7$.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 1 2 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 3 4 5 1 2 |
1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
16 7 16 11 1 8 2 4 5 10 14 3 15 12 9 13 6 |
92 |
