# Automorphisms

### Memory limit: 32 MB

**A tournament** is a directed graph in which:

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

Let

denote any permutation of the set of tournament's vertices. (A permutation of a finite set is an injective function from

to

.) The permutation

is called

**an automorphism**, if for each two different vertices u and v the direction of the edge between

and

is the same as the direction of the edge between

and

(i.e.

is an edge in the tournament if and only if

is an edge in this tournament). For a given permutation

, we want to know for how many tournaments this permutation is an automorphism.

## Example

Let's take the set of vertices and the permutation :
, , , .
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 standard input,
- computes , the number of different -element tournaments for which this permutation is an automorphism,
- writes to the standard output
**the remainder of dividing by **

## Input

In the first line of the standard input there is one integer , , which is the number of vertices. In the following lines there is a description of a permutation . We assume that vertices are numbered from 1 to . In line there is a value of the permutation for the vertex (i.e. the value ).

## Output

In the first and only line of the standard output there should be one integer equal to the remainder of dividing (the number of different -vertex tournaments for which is an automorphism) by .

## Example

For the input data:

4
2
4
3
1

the correct result is:

4

*Task author: Grzegorz Jakacki.*