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

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