Tańce w kółkach

Limit pamięci: 32 MB

Do pewnego przedszkola chodzi dzieci, które codziennie ustawiają się w kółek i tańczą. W każdym kółku tańczy co najmniej dzieci. Dwa ustawienia dzieci uważamy za różne, jeżeli pewne dziecko w jednym ustawieniu ma innego sąsiada po swojej prawej stronie niż w drugim. Twoim zadaniem jest obliczenie liczby wszystkich różnych ustawień modulo . Jeżeli nie ma ustawień spełniających opisane warunki, poprawnym wynikiem jest .

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia liczby , oraz ,
• obliczy liczbę , gdzie jest liczbą różnych ustawień dzieci ( oznacza resztę z dzielenia przez ),
• wypisze na standardowe wyjście.

Wejście

Pierwszy i jedyny wiersz standardowego wejścia zawiera trzy liczby całkowite oddzielone pojedynczymi odstępami: - liczba dzieci (), - liczba kółek () oraz - minimalna liczba dzieci w każdym kółku ().

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę: .

Przykład

Dla danych wejściowych:

7 2 3

poprawną odpowiedzią jest:

420

Autor zadania: Krzysztof Sikora.