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$.

-----Examples-----
Sample Input 1:
2
1 2
Sample Output 1:
2

Sample Input 2:
5
3 4 5 1 2
Sample Output 2:
1

见题面

见题面