Bajtazar chciał kupić babci kolorowy naszyjnik z korali. Niestety w pobliskim sklepie były dostępne tylko naszyjniki jednobarwne, więc Bajtazar nabył jeden z nich i postanowił go przemalować tak, żeby po założeniu naszyjnika na szyję żadne dwa sąsiednie korale nie miały tego samego koloru. Zastanawia się on, na ile różnych sposobów może to uczynić zakładając, że ma do dyspozycji k różnych kolorów farb i chciałby pomalować każdy koral z użyciem jednej z nich.
Przy liczeniu liczby pokolorowań weź pod uwagę, że dla Bajtazara wszystkie korale są rozróżnialne.
Napisz program, który:
Pierwszy i jedyny wiersz wejścia zawiera trzy liczby całkowite n, k oraz m (1 <= n <= 1018, 1 <= k <= 106, 2 <= m <= 109), pooddzielane pojedynczymi odstępami i oznaczające odpowiednio liczbę korali w naszyjniku, liczbę dostępnych kolorów i ... liczbę m.
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą - resztę z dzielenia przez m liczby różnych pokolorowań naszyjnika.
Dla wejścia:
3 3 10
prawidłowym rozwiązaniem jest:
6
Możliwe pokolorowania naszyjnika to: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).
[Zgłoś rozwiązanie] [Moje zgłoszenia]