Mrówka
Limit pamięci: 32 MB
Myśląca bajtocka mrówka chodzi po krawędziach sześcianu ABCDEFGH:
Zastanawia się, na ile sposobów może przejść z zadanego wierzchołka
sześcianu do wskazanego innego, przechodząc dokładnie po krawędziach
(jeżeli mrówka zaczyna iść po danej krawędzi, to nigdy nie zawróci
i kiedyś dojdzie do drugiego jej końca). Jeżeli mrówka przejdzie
razy po tej samej krawędzi, to krawędź tą liczymy razy.
Mrówka chciałaby, żeby jej trasa była ciekawa, to znaczy, jeżeli w pewnym
momencie mrówka wejdzie po pewnej krawędzi do danego wierzchołka, to
nie chciałaby wyjść z tego wierzchołka w kolejnym kroku po tej samej krawędzi.
Ponieważ mrówka potrafi jedynie liczyć od do , dla pewnego , to podaj jej tylko
resztę z dzielenia przez liczby możliwych tras, spełniających
powyższe warunki.
Zadanie
Napisz program który:
-
wczyta ze standardowego wejścia początkowy i końcowy wierzchołek na
trasie mrówki, liczbę krawędzi do pokonania i liczbę ,
-
obliczy resztę z dzielenia przez liczby ciekawych tras mrówki
spełniających jej wymagania,
-
wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajdują się dwie wielkie litery i
(, ), oddzielone pojedynczym odstępem i
oznaczające wierzchołki początkowy i końcowy na trasie mrówki.
Drugi wiersz wejścia zawiera dwie liczby całkowite i
(, ),
oddzielone pojedynczym odstępem.
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia należy zapisać jedną
liczbę całkowitą - resztę z dzielenia przez liczby ciekawych tras
mrówki z wierzcholka do wierzchołka , złożonych z dokładnie
krawędzi sześcianu.
Przykład
Dla danych wejściowych:
A B
3 100
poprawną odpowiedzią jest:
2
Autor zadania: Jakub Radoszewski.