시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB296604318.943%

문제

동민이는 HCPC에 나갈지 말지 고민하는 사람 $N$명 중 $3$명을 뽑아 팀을 만들어주려 한다.

각 사람들은 $1$부터 $N$까지 번호가 차례대로 매겨져 있다. 이 중에는 원하는 사람 한 명과 같은 팀이어야 참가하는 사람도 있고, 원하는 사람이 없어 누구와 같은 팀이든 상관없이 참가할 수 있는 사람도 있다.

동민이는 각 사람이 원하는 사람이 있는지, 있다면 누구인지 모두 조사해 두었다. 하지만 어떤 조합으로 $3$인 팀을 만들 수 있는지는 아직 구하지 못했다. 동민이를 위해 $3$인 팀을 만들 수 있는 경우의 수를 계산하는 프로그램을 작성해 주자. 단, 답이 너무 커질 수 있으니 경우의 수를 $10^9+7$로 나눈 나머지를 출력한다.

입력

첫째 줄에 사람의 수를 의미하는 정수 $N$이 주어진다. $(1\leq N\leq 500\, 000)$

둘째 줄에 $N$개의 정수 $A_1$, $A_2$, $\cdots$, $A_N$이 공백으로 구분되어 주어진다. $A_i=i$라면 $i$번 사람은 원하는 사람이 없다는 의미이며, 아니라면 $A_i$는 $i$번 사람이 원하는 사람의 번호를 의미한다. $(1\le A_i\le N)$

출력

$N$명의 사람 중 $3$명을 뽑아 하나의 팀을 구성하는 경우의 수를 $10^9+7$로 나눈 나머지를 출력한다.

예제 입력 1

5
2 1 1 4 5

예제 출력 1

3

$1$번 사람은 $2$번과, $2$번과 $3$번 사람은 $1$번과 같은 팀이어야 대회에 참가한다. $4$번과 $5$번 사람은 팀원이 누구든 대회에 참가할 수 있다. 따라서 가능한 조합은 $(1,2,3)$, $(1,2,4)$, $(1,2,5)$ 세 가지 뿐이다.