A tournament is a directed graph in which:

• for each two different vertices u and v there exsits exactly one edge between them (i.e. either u -> v or v -> u),
• there are no loops (i.e. for each vertex u there is no edge u-> u ).

Let p denote any permutation of the set of tournament's vertices. (A permutation of a finite set is an injective function from X to X.) The permutation p is called an automorphism, if for each two different vertices u and v the direction of the edge between u and v is the same as the direction of the edge between p(u) and p(v) (i.e. u -> v is an edge in the tournament if and only if p(u) -> p(v) is an edge in this tournament). For a given permutation p, we want to know for how many tournaments this permutation is an automorphism.

Example

Let's take the set of vertices 1,...,4 and the permutation p:

There are only four tournaments for which this permutation is an automorphism:

Task

Write a program which:

• reads the description of a permutation of an n-element set from the text file AUT.IN,
• computes t, the number of different n-element tournaments for which this permutation is an automorphism,
• writes to the text file AUT.OUT the remainder of dividing t by 1000

Input

In the first line of the text file AUT.IN there is one integer n, 1<=n<= 10000, which is the number of vertices. In the following n lines there is a description of a permutation p. We assume that vertices are numbered from 1 to n. In line (k+1) there is a value of the permutation p for the vertex k (i.e. the value p(k)).

Output

In the first and only line of the text file AUT.OUT there should be one integer equal to the remainder of dividing t (the number of different n-vertex tournaments for which p is an automorphism) by 1000.

Example

For the input file AUT.IN

4
2
4
3
1

The correct answer is the output file AUT.OUT

4