자기동형사상

토너먼트(tournament)는 다음 조건을 만족하는 방향 그래프다.

• 서로 다른 두 정점 $u$, $v$ 사이에는 정확히 하나의 간선이 존재한다. 즉 $u \to v$ 또는 $v \to u$ 중 하나만 있다.
• 자기 자신으로 가는 간선(루프)은 없다. 즉 모든 정점 $u$에 대해 $u \to u$ 간선은 존재하지 않는다.

$p$를 토너먼트의 정점 집합 위의 순열이라 하자. (유한 집합 $X$의 순열이란 $X$에서 $X$로 가는 전단사 함수다.) 순열 $p$가 자기동형사상(automorphism)이라는 것은, 서로 다른 모든 두 정점 $u$, $v$에 대해 $u$와 $v$ 사이 간선의 방향이 $p(u)$와 $p(v)$ 사이 간선의 방향과 같다는 뜻이다. 즉 $u \to v$가 간선인 것과 $p(u) \to p(v)$가 간선인 것이 서로 동치다. 주어진 순열 $p$에 대해, $p$를 자기동형사상으로 갖는 토너먼트가 몇 개인지 구하려 한다.

예를 들어 정점 집합 $\{1, \dots, 4\}$와 순열 $p(1)=2$, $p(2)=4$, $p(3)=3$, $p(4)=1$을 생각하자. 이 순열을 자기동형사상으로 갖는 토너먼트는 정확히 네 개뿐이다.

다음을 수행하는 프로그램을 작성하라.

• 표준 입력에서 $n$개의 원소로 이루어진 집합의 순열 정보를 읽는다.
• 이 순열을 자기동형사상으로 갖는 서로 다른 $n$개 정점 토너먼트의 개수 $t$를 계산한다.
• $t$를 $1000$으로 나눈 나머지를 표준 출력에 쓴다.

첫째 줄에 정점의 개수를 나타내는 정수 $n$ ($1 \le n \le 10000$)이 주어진다. 정점은 $1$번부터 $n$번까지 번호가 매겨져 있다. 이어지는 $n$개의 줄 중 $k+1$번째 줄에는 정점 $k$에서의 순열 값 $p(k)$가 주어진다.

$p$를 자기동형사상으로 갖는 서로 다른 $n$개 정점 토너먼트의 개수 $t$를 $1000$으로 나눈 나머지를 한 줄에 출력한다.