Owce

Limit pamięci: 32 MB

Mieszkańcy wyżyny Bajtockiej z dziada-pradziada trudnią się hodowlą owiec. Każdy szanujący się hodowca posiada ogrodzone pastwisko w kształcie wielokąta wypukłego¹, na którym wypasa swoje owce. Każda szanująca się owca ma swoje ulubione miejsce na pastwisku, gdzie codziennie skubie trawę. Od czasu do czasu owce lubią się też pobawić. Ponieważ owce bawią się parami, każdy pastuch posiada parzystą liczbę owiec, tak żeby każda owca miała zawsze partnera do zabawy.

Niepokój pastuchów wzbudziło rozporządzenie wydane przez bajtogrodzkiego komisarza ds. rolnictwa. Głosi ono, że od nowego roku owce można wypasać tylko na pastwiskach w kształcie trójkątów. Każdy hodowca, którego pastwisko jest -kątem dla , musi je podzielić na trójkąty, stawiając na jego terenie płotów. Pojedynczy płot musi mieć kształt odcinka łączącego dwa wierzchołki wielokąta stanowiącego całe pastwisko. Płoty nie mogą przecinać się poza wierzchołkami wielokąta. Bez spełnienia warunku komisarza hodowcy nie otrzymają dopłaty do hodowli posiadanych owiec.

Bajtazar, który jest hodowcą owiec, musi zadecydować, jak podzielić swoje pastwisko. Głowi się teraz, ile jest w ogóle sposobów, na jakie można podzielić jego pastwisko tak, aby żaden płot nie przechodził przez ulubione miejsce żadnej owcy i wszystkie owce nadal mogły się bawić, czyli aby w każdym trójkącie znajdowały się ulubione miejsca wypasu parzystej liczby owiec. Pomóż mu i napisz odpowiedni program!

Wejście

Pierwszy wiersz standardowego wejścia zawiera trzy liczby całkowite , oraz (, , , ) pooddzielane pojedynczymi odstępami, oznaczające odpowiednio: liczbę wierzchołków wielokąta stanowiącego pastwisko, liczbę owiec oraz pewną dodatnią liczbę całkowitą . W kolejnych wierszach znajdują się po dwie liczby całkowite i () oddzielone pojedynczym odstępem, oznaczające współrzędne -tego wierzchołka pastwiska. Wierzchołki te są podane w kolejności zgodnej z ruchem wskazówek zegara. W kolejnych wierszach znajdują się po dwie liczby całkowite , () oddzielone pojedynczym odstępem, oznaczające współrzędne ulubionego miejsca -tej owcy. Ulubione miejsce każdej owcy znajduje się wewnątrz (tj. nie na brzegu) pastwiska.

Wyjście

Twój program powinien wypisać na standardowe wyjście jedną liczbę całkowitą, oznaczającą resztę z dzielenia przez liczby takich podziałów pastwiska na trójkąty, aby żaden płot nie przechodził przez ulubione miejsce żadnej owcy i w każdym powstałym trójkącie znajdowały się ulubione miejsca parzystej liczby owiec.

Przykład

Dla danych wejściowych:

5 4 10
5 5
3 0
-1 -1
-3 4
1 10
1 0
-1 0
1 6
-2 5

poprawną odpowiedzią jest:

3

Na rysunku przedstawiono trzy możliwe sposoby podziału pastwiska na trójkąty. Kropkami zaznaczono ulubione miejsca owiec.

Autor zadania: Michał Włodarczyk.