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 ).
Oznaczmy przez dowolną permutację zbioru wierzchołków turnieju. (Permutacją skończonego zbioru nazywamy każdą różnowartościową funkcję z w .) Permutację nazywamy automorfizmem, jeżeli dla dowolnych dwóch różnych wierzchołków i zwrot krawędzi pomiędzy i jest taki sam, jak pomiędzy i (tzn. jest krawędzią w turnieju wtedy i tylko wtedy, gdy jest krawędzią w tym turnieju). Dla zadanej permutacji interesuje nas, dla ilu turniejów jest ona automorfizmem.

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.