Hide

Problem G
Chair Hopping

/problems/chairhopping/file/statement/en/img-0001.png
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 \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

Please log in to submit a solution to this problem

Log in