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.
Kontakt
W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem szkopul@fri.edu.pl.
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, odwiedź nasze serwery na Discordzie. Są one moderowane przez społeczność, ale członkowie zespołu wsparcia również aktywnie się tam udzielają.