Zliczanie planów sieci drogowej
Limit pamięci: 64 MB
Bajtazar wybiera się w podróż samochodową po Bajtocji, lecz niestety
ma problemy z nabyciem mapy tego kraju.
Od znajomych dowiedział się o pewnych właściwościach bajtockiej sieci dróg:
- W Bajtocji jest miast, ponumerowanych od do .
- Każda droga jest dwukierunkowa i łączy ze sobą pewne dwa
różne miasta.
- Każde dwa różne miasta są połączone dokładnie jedną trasą,
złożoną z jednej bądź większej liczby dróg, na której żadne miasto się nie
powtarza.
- Najdłuższa z tras, na której żadne miasto się nie powtarza,
składa się z dróg.
Na podstawie zdobytych informacji Bajtazar zamierza spróbować odtworzyć
mapę drogową Bajtocji.
Żeby się nadmiernie nie napracować, Bajtazar chciałby wiedzieć, ile jest
różnych planów sieci drogowej spełniających podane warunki.
Przy porównywaniu planów Bajtazar nie bierze pod uwagę dokładnych lokalizacji
zaznaczonych miast, a jedynie schemat połączeń; nie interesują go także
konkretne numery miast.
Innymi słowy, Bajtazar uznaje dwa plany za jednakowe wtedy i tylko wtedy,
gdy można miastom z jednego z nich przyporządkować różnowartościowo miasta
z drugiego tak, że jeżeli miasta
i
są połączone drogą na pierwszym
planie, to ich odpowiedniki
i
są także połączone drogą na drugim
planie.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia liczby , oraz ,
- wyznaczy liczbę różnych planów sieci drogowej, zgodnych
z informacjami zdobytymi przez Bajtazara, modulo ,
- wypisze wynik na standardowe wyjście.
Wejście
Pierwszy i jedyny wiersz wejścia zawiera trzy liczby całkowite ,
oraz (, , , jest liczbą
pierwszą), pooddzielane pojedynczymi odstępami.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą
- resztę z dzielenia przez liczby różnych planów, spełniających warunki
znane Bajtazarowi.
Przykład
Dla danych wejściowych:
6 3 13
poprawną odpowiedzią jest:
2
Autor zadania: Jakub Radoszewski.