Superszybkie wyścigi w kółko

Limit pamięci: 32 MB

Kółko Miłośników Super Szybkich Symultanicznych Wyścigów w Kółko w Spidlandii (w skrócie KMSSSWwKwS) postanowilo pobić rekord ilości przejeżdzanych tras w odbywających sie jednocześnie wyścigach w kółko. Aby pobić rekord Kółko musi zorganizować na swoich trasach jeden lub więcej wyscigów tak, aby sumaryczna ilość użytych tras wynosiła , gdyż poprzedni rekord wynosi . Trasy Kółka w Spidlandi biegną między skrzyżowaniami, na każdej z tras można poruszać sie tylko w jednym kierunku. Każdy wyścig musi odbywać sie na zamkniętym ciągu tras, tak aby można było jeździć w kółko. Ze względu na bezpieczeństwo zawodników dwa wyścigi nie mogą biec tą samą trasą, ani przez to samo skrzyżowanie, oraz żaden wyścig nie może dwa razy przechodzić przez to samo skrzyżowanie. Wiadomo, że z każdego skrzyżowania wychodzą co najwyżej dwie trasy i do każdego skrzyżowania wchodzą co najwyżej dwie trasy. Żadna trasa nie zaczyna się i nie kończy na tym samym skrzyżowaniu. Twoim zadaniem jest stwierdzenie, czy na trasach KMSSSWwKwS mogą zostać wytyczone wyścigi tak, aby ich łączna długość (ilość użytych tras) wynosiła i jeżeli tak, to wyznaczenie liczby możliwych sposobów wytyczenia takich wyścigów.

Zadanie

Napisz program, który:

• wczyta opisy tras KMSSSWwKwS,
• stwierdzi, czy na tych trasach mogą odbyć się wyścigi o łącznej długości i jeżeli tak, to wyznaczy ilość sposobów zorganizowania takich wyścigów,
• wypisze wielkimi literami słowo lub resztę z dzielenia przez 10000 liczby sposobów zorganizowania wyścigów.

Wejście

W pierwszym wierszu znajdują się dwie liczby całkowite i oddzielone spacją, i . Liczba to liczba skrzyżowań i jednocześnie rekord łącznej długości tras wyścigów jaki chciałoby ustanowić kółko. Natomiast , to liczba wszystkich tras kółka. W każdym z kolejnych wierszy zapisany jest opis każdej jednej trasy składający się z dwóch liczb całkowitych i oddzielonych spacją i oznaczających, że dana trasa wychodzi ze skrzyżowania i kończy sie na skrzyżowaniu .

Wyjście

Wyjście powinno zawierać zawierać jedno słowo , jeśli na zadanch trasach nie można zorganizować wyścigów o łącznej długości , lub jedną liczbę całkowitą równą reszcie z dzielenia przez 10 000 liczby sposobów zorganizowania takich wyścigów.

Przykład

Dla danych wejściowych:

3 6
1 2
1 3
2 1
2 3
3 1
3 2

poprawną odpowiedzią jest:

2