HCPC Team Formation

Time limit1sMemory limit1024 MB

Summary

Count the 3-person teams where every member's preferred partner, if they have one, is also on the team.

Level: Medium6 of 10
Topics: Combinatorics, Graph, Implementation
Solved: No attempts yet

Problem

Dongmin wants to form a team of $3$ from $N$ people who are deciding whether to join HCPC.

The people are numbered from $1$ to $N$ . Some of them join only if they are on a team with the one person they want. Others have no preference and can join with anyone.

Dongmin has surveyed each person to find out whether they have a preferred partner and, if so, who it is. He has not yet worked out which groups of $3$ can form a team. Write a program that counts the number of ways to form a team of $3$ for Dongmin. Since the count can be very large, print it modulo $10^9+7$ .

Input

The first line contains an integer $N$ , the number of people. $(1 \le N \le 500\,000)$

The second line contains $N$ integers $A_1, A_2, \cdots, A_N$ separated by spaces. If $A_i = i$ , person $i$ has no preferred partner. Otherwise, $A_i$ is the number of the person that person $i$ wants to be with. $(1 \le A_i \le N)$

Output

Print the number of ways to choose $3$ of the $N$ people to form one team, modulo $10^9+7$ .

Examples1

Example 1
Input
```
5
2 1 1 4 5
```
Expected output
```
3
```