Ewakuacja

W bitocji trwa wojna i komunizm. Prawdopodobnie za kilka godzin nuke uderzy w jedno z miast bitocji. Obecnie sztab generalny opracowuje PDECP (Plan pięcioletni Ewakuacji Centralnie Planowanej). Już przed rozpoczęciem wojny zauważono, że planowanie takiej ewakuacji może być bardzo trudne i nie ma pewności czy partyjni informatycy będą wstanie go rozwiązać. Dlatego zawczasu postanowiono problem uprościć. W tym celu poblokowano drogi w bitocji tak, by między każdymi dwoma miastami istniała dokładnie jedna droga. Na razie trwa specjalne zgromadzenie partii obradujące nad zaistniałą sytuacją. Jednak już teraz bitoccy informatycy zastanawiają się jak trudny problem przyszło im rozwiązać. Lękają się że wymagania głównego sekretarza mogą się okazać trudne obliczeniowo i że konieczne będzie analizowania każdego możliwego przypadku oddzielnie. Chcą się dowiedzieć czy wystarczy im na to siły robotniczej. W tym celu kazali Tobie policzyć ilość możliwych sposobów ewakuacji ludności. Znane są Ci ilości towarzyszy w każdym z bitockich miast oraz rozkład dróg między nimi. Wiadomo też w które miasto uderzy nuke. Ustalono, że podczas ewakuacji każdy będzie uciekał w ten sposób, aby odległość od zbombardowanego miasta ciągle się zwiększała (kazanie obywatelom zbliżania się tam mogłoby doprowadzić do kryzysu zaufania i wykształcenia się rewolucyjnych bajtówek). Z tego powodu pozwolono też każdy będzie uciekał tak długo jak może. Pamiętaj że, zgodnie z doktryną, wszyscy robotnicy są sobie równi i nierozróżnialni.Chodzaż w dobie kryzysu wartości i to może ulec zmianie. Infmatycy chcą być przygotowani i na tę możliwość, dlatego na wejściu będzie podane, czy obywatele są rozróżnialni czy nie. Ponieważ wynik może być bardzo duży, postanowiono skorzystać z Robotniczego Twierdzenia o Resztach. Wystarczy więc, że podasz wynik modulo pewna dana liczba pierwsza p.

Wejście

W kolejce stoją: n, m, p, r (1 ≤ n ≤ 20000, 1 ≤ m ≤ n, 2 ≤ p ≤ 1000000009, r ∈ {0,1}), oznaczające odpowiednio liczbę miast w bitocji, numer miasta które zostanie zbombardowane, liczbę pierwszą p i liczbę r. r=1 gdy obywatele są rozróżnialni i r=0 gdy obywatele są nierozróżnialni. W następnych wierszach stoi (n-1) par liczb oznaczających numery miast połączonych niezablokowaną drogą (miasta są numerowane liczbami od 1 do n). W następnych n wierszach jest podana liczba obywateli w i-tym mieście. Ta liczba jest z przedziału [0,400].

Wyjście

Należy wyprodukować jedną liczbę oznaczającą liczbę możliwych sposobów ewakuacji modulo p. Gdy obywatele są nierozróżnialni to dwie ewakuacje są sobie równe gdy multizbiory tras ewakuowanej ludności są sobie równe.

Możesz założyć, że w testach wartych 50% punktów r=1.

Przykład

Dla danych wejściowych:

8 3 1000000009 1
6 7
2 6
3 6
4 3
5 6
5 8
4 1
5
3
3
4
5
3
4
2

poprawną odpowiedzią jest:

1728

a dla danych wejściowych:

8 3 1000000009 0
6 7
2 6
3 6
4 3
5 6
5 8
4 1
5
3
3
4
5
3
4
2

poprawną odpowiedzią jest:

200