Automorphisms

A tournament is a directed graph in which:

• for every two distinct vertices $u$ and $v$ there is exactly one edge between them (either $u \to v$ or $v \to u$),
• there are no loops (for every vertex $u$ there is no edge $u \to u$).

Let $p$ be a permutation of the tournament's vertices. (A permutation of a finite set $X$ is a bijection from $X$ to $X$.) The permutation $p$ is an automorphism if for every two distinct vertices $u$ and $v$ the edge between $u$ and $v$ points in the same direction as the edge between $p(u)$ and $p(v)$; that is, $u \to v$ is an edge if and only if $p(u) \to p(v)$ is an edge. For a given permutation $p$ we want to know how many tournaments have $p$ as an automorphism.

For example, take the vertex set $\{1, \dots, 4\}$ and the permutation $p$ with $p(1)=2$, $p(2)=4$, $p(3)=3$, $p(4)=1$. There are exactly four tournaments for which this permutation is an automorphism:

Write a program that:

• reads the description of a permutation of an $n$-element set from standard input,
• computes $t$, the number of distinct $n$-vertex tournaments for which this permutation is an automorphism,
• writes to standard output the remainder of $t$ divided by $1000$.

The first line contains one integer $n$ ($1 \le n \le 10000$), the number of vertices. The vertices are numbered from $1$ to $n$. Each of the next $n$ lines contains one integer: line $k+1$ holds $p(k)$, the value of the permutation at vertex $k$.

Print one integer: the remainder of $t$ divided by $1000$, where $t$ is the number of distinct $n$-vertex tournaments for which $p$ is an automorphism.