Zadanie: Dziuple

W Bajtocji rosną dwa bardzo wysokie pionowe drzewa, a w każdym z nich są wydrążone jedna pod drugą dziuple dla ptaków. Pewnego dnia w dziuplach postanowiło zamieszkać n bardzo szybkich ptaszków. Niektóre ptaszki znają się wzajemnie, więc po wprowadzeniu się chciałyby mieć możliwość odwiedzania się nawzajem w swoich dziuplach. Ptaszki latają bardzo szybko i zawsze po liniach prostych. Chcąc uniknąć niebezpieczeństwa zderzenia postanowiły rozlokować się w dziuplach w taki sposób, żeby:

każde dwa ptaszki, które chciałyby się odwiedzać, mieszkały na różnych drzewach, oraz
dla dowolnych dwóch par znajomych ptaszków, odcinki łączące dziuple znajomych ptaszków nie przecinały się (co najwyżej mogą mieć wspólny koniec).

Dodatkowo, ptaszki chcą mieszkać jak najniżej. Na każdym z drzew zajmują więc pewną liczbę dolnych dziupli. W każdym z drzew jest więcej dziupli niż wszystkich ptaszków.

Jak wiadomo, ptaszki mają niewielkie rozumki. Dlatego też poprosiły Cię -- znanego ornitologa -- o pomoc w sprawdzeniu, na ile różnych sposobów mogą rozlokować się w dziuplach.

Zadanie

Napisz program, który:

wczyta ze standardowego wejścia opis relacji znajomości wśród ptaszków,
obliczy, na ile różnych sposobów można rozmieścić ptaszki w dziuplach spełniając podane powyżej wymagania,
wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia zapisano trzy liczby całkowite n, m oraz k, oznaczające odpowiednio: liczbę ptaszków, liczbę różnych par ptaszków znających się nawzajem oraz liczbę której należy użyć przy podawaniu wyniku (por. p. Wyjście), 2 <= n <= 1 000 000, 1 <= m <= 10 000 000, 2 <= k <= 2 000 000. Ptaszki są ponumerowane od 1 do n. W kolejnych m wierszach podane są pary znających się nawzajem ptaszków, po jednej parze w wierszu. W i + 1-ym wierszu są zapisane dwie liczby całkowite a_i i b_i oddzielone pojedynczym odstępem, 1 <= a_i, b_i <= n, a_i <> b_i. Są to numery znajomych ptaszków. Każda (nieuporządkowana) para znajomych ptaszków jest podana dokładnie raz.

Wyjście

Niech r będzie liczbą różnych rozmieszczeń ptaszków w dziuplach, spełniających podane warunki. Twój program powinien wypisać w pierwszym wierszu wyjścia jedną liczbę całkowitą: resztę z dzielenia r przez k. Jeżeli nie istnieje szukane rozmieszczenie ptaszków, to poprawnym wynikiem jest 0.

Przykład

Dla danych wejściowych:

3 2 10
1 2
1 3

poprawną odpowiedzią jest:

Wersja do druku