32868번 - HCPC 팀 짜기

문제

동민이는 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$로 나눈 나머지를 출력한다.

제한

노트