Idempotent Functions

Memory limit: 64 MB

You are given a positive integer . By we mean the set . Function is called a permutation if it is injective (for distinct arguments returns distinct values). Function is called idempotent if for every holds .

You are given a function . How many pairs of functions satisfy following conditions:

• is a permutation,
• is idempotent,
• for every holds ?

Task

Write a program which:

• reads number and description of function from the standard input ,
• determines the number of pairs of functions satisfying the requirement described above,
• writes the result to the standard output.

Input

In the first line of input there is one integer (). Second line contains a description of function : () for , separated with single spaces.

Output

In the first line of output there should be a single integer: the remainder of the division by of the number of different pairs of functions satisfying the requirement.

Example

For the input data:

8
7 4 5 1 7 4 4 1

the correct result is:

288

Task author: Marcin Pilipczuk.