Hide

Problem O
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 si. The values of si 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 ti. Observing that, you wonder in how many ways the values of si can be chosen. The answer can be large. Output it modulo 109+7.

Input

The first line of the input contains the integer n (1n105). The second line of the input contains n distinct integers t1,t2,tn (1tin).

Output

Output the number of ways in which the values of si can be chosen, modulo 109+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
Hide

Please log in to submit a solution to this problem

Log in