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
is a permutation,
for every holds ?
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.
In the first line of input there is one integer ().
Second line contains a description of function : () for ,
separated with single spaces.
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.