Prąd

Limit pamięci: 64 MB

Rada wsi Bajtion zdecydowała się na wykorzystanie naturalnych źródeł energii elektrycznej do zasilania gospodarstw i postanowiła wybudować dużo wiatraków. Ponieważ wszystkie bajtiońskie gospodarstwa znajdują się w jednej linii, po tej samej stronie jedynej we wsi drogi, to i wszystkie wiatraki wybudowano w jednej linii, ale po drugiej stronie tej drogi. Pewne wiatraki połączono z pewnymi gospodarstwami za pomocą linii wysokiego napięcia, które biegną nad drogą. Jeden wiatrak mógł zostać połączony z wieloma gospodarstwami, a jedno gospodarstwo - z wieloma wiatrakami; podobnie, pewne gospodarstwa lub jakieś wiatraki mogły nie zostać w ogóle połączone. Każde połączenie elektryczne biegnie dokładnie w linii prostej. Ponadto między dowolnym gospodarstwem a wiatrakiem została poprowadzona co najwyżej jedna linia wysokiego napięcia.

Bajtockim energetykom nie do końca spodobał się projekt rady; uważają oni, że dużo wydajniejszym rozwiązaniem jest sytuacja, w której każdy wiatrak zasila co najwyżej jedno gospodarstwo, a każde gospodarstwo jest zasilane za pomocą co najwyżej jednego wiatraka. Ponadto funkcjonujące linie wysokiego napięcia według energetyków nie mogą biec nad tymi samymi punktami (czyli mieć wspólnych punktów, jeżeli na nie spojrzeć z lotu ptaka, czyli jak na odcinki na płaszczyźnie), gdyż silne bajtockie wiatry powodują powstawanie w wiatrakach prądu o wysokim natężeniu i przecinające się linie negatywnie ze sobą oddziałują.

Rada wsi poprosiła Cię o napisanie programu, który wyznaczy liczbę sposobów wyboru pewnych spośród już poprowadzonych linii wysokiego napięcia, które miałyby pozostać (pozostałe zostaną zlikwidowane), tak aby końcowy układ był zgodny z radami energetyków. Ponieważ rada wsi nie lubi operować dużymi liczbami, wystarczy jeżeli obliczysz dla niej resztę z dzielenia wyniku przez podaną przez radę liczbę.

Zadanie

Napisz program, który:

• wczyta opis już poprowadzonych linii wysokiego napięcia,
• wyznaczy resztę z dzielenia liczby sposobów poprawnego połączenia którychś gospodarstw z którymiś wiatrakami przez liczbę podaną przez radę wsi,
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera cztery liczby całkowite , , oraz (, , ), pooddzielane pojedynczymi odstępami i oznaczające odpowiednio: liczbę gospodarstw we wsi, liczbę wybudowanych wiatraków, liczbę poprowadzonych linii wysokiego napięcia oraz liczbę podaną przez radę wsi. Gospodarstwa są ponumerowane liczbami naturalnymi od do , a wiatraki - liczbami od do . Gospodarstwa są rozmieszczone przy drodze w kolejności od pierwszego do -tego, a z drugiej strony drogi stoją wiatraki w kolejności od pierwszego do -tego.

Kolejne wierszy zawiera po dwie liczby całkowite i (, dla ), oddzielone pojedynczym odstępem i definiujące -te połączenie łączące gospodarstwo o numerze z wiatrakiem o numerze .

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, oznaczającą resztę z dzielenia liczby poprawnych sposobów połączenia gospodarstw z wiatrakami przez .

Przykład

Dla danych wejściowych:

3 3 5 100
1 2
2 3
3 1
2 1
3 2

poprawną odpowiedzią jest:

8

Wyjaśnienie do przykładu: Na 1 sposób możemy nie wybrać żadnego połączenia (jest to decyzja mało sensowna, ale zgodna z radami energetyków...), na 5 sposobów możemy wybrać tylko jedno połączenie, na 2 sposoby możemy wybrać dwa połączenia, a w żaden sposób nie możemy wybrać trzech połączeń.

Autor zadania: Jakub Radoszewski.