Mrówka
Mrówka chodzi po krawędziach sześcianu ABCDEFGH:
Zastanawia się, na ile sposobów może przejść z danego wierzchołka sześcianu do danego innego, przechodząc dokładnie po k 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). 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 po tej samej krawędzi.
Ponieważ mrówka potrafi jedynie liczyć od 0 do p-1, to podaj jej tylko resztę z dzielenia przez p liczby możliwych tras, spełniających powyższe warunki.
Zadanie
Napisz program który:
- wczyta ze standardowego wejścia wierzchołki początkowy i końcowy na trasie mrówki, liczbę krawędzi na jej trasie i liczbę p,
- obliczy resztę z dzielenia przez p 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 duże litery v1 i v2 (A <= v1,v2 <= H, v1 różne od v2), 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 k i p (1 <= k <= 2.000.000.000, 2 <= p <= 1.000.000.000), 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 p liczby ciekawych tras mrówki z wierzcholka v1 do wierzchołka v2, złożonych z dokładnie k krawędzi sześcianu.
Przykład
Dla danych wejściowych:
A B 3 100
poprawnym wynikiem jest:
2
