Automorfizmy
Limit pamięci: 32 MB
Turniejem nazywamy graf skierowany, w którym:
- dla dowolnych dwóch różnych wierzchołków i istnieje dokładnie jedna krawędź pomiędzy tymi wierzchołkami (tzn. albo , albo ),
- nie istnieją pętle (tzn. dla dowolnego wierzchołka nie ma krawędzi ).
Przykład
Weźmy zbiór wierzchołków oznaczonych liczbami oraz permutację : , , , . Istnieją tylko cztery turnieje, dla których ta permutacja jest automorfizmem:
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis permutacji -elementowego zbioru wierzchołków,
- obliczy liczbę różnych -wierzchołkowych turniejów, dla których ta permutacja jest automorfizmem,
- wypisze na standardowe wyjście resztę z dzielenia przez .
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba naturalna , , będąca liczbą wierzchołków.
W kolejnych wierszach znajduje się opis permutacji . Zakładamy, że wierzchołki są ponumerowane liczbami od 1 do . W wierszu -szym znajduje się wartość permutacji dla wierzchołka nr (tzn. wartość ).
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia powinna znaleźć się jedna liczba całkowita będąca resztą z dzielenia przez liczby różnych -wierzchołkowych turniejów, dla których permutacja jest automorfizmem.
Przykład
Dla danych wejściowych:
4 2 4 3 1
poprawną odpowiedzią jest:
4
Autor zadania: Grzegorz Jakacki.