Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_14_05 - Spływ kajakowy

Narew i BiebrzaW pewnym kraju płynie niezwykła rzeka. Ma ona mnóstwo rozgałęzień i bocznych koryt, co tworzy prawdziwy labirynt kanałów wodnych. W niektórych miejscach umieszczono punkty wypożyczania kajaków – można tam zarówno wziąć kajak, jak i go zwrócić. Oczywiście punkty te są połączone kanałami. Franek jest amatorem spływów kajakowych i chce zaprosić swoją koleżankę Franię na spływ, by jej zaimponować umiejętnościami kajakowymi w wodnym labiryncie. Zachwala on Frani taką formę relaksu mówiąc, że różnych tras spływu jest więcej niż dni w roku i nie można się po prostu nudzić. Czy na pewno ma rację? Frania jest ciekawa, ile dokładnie jest takich tras, a on nie chce wyjść na głupca. Pomóż mu! Na podstawie położenia kanałów i punktów wypożyczeń oblicz, ile jest różnych tras spływów (płyniemy tylko w dół). Punkty rozpoczęcia i zakończenia tras mogą być dowolne.

Wejście

W pierwszej linii wejścia podane są dwie, oddzielone spacjami liczby całkowite n oraz m (2<=n<=100000, 1<=m<=1000000) oznaczające odpowiednio liczbę punktów wypożyczeń i liczbę kanałów. W kolejnych m liniach znajdują się po dwie liczby całkowite ai oraz bi (z zakresu od 1 do n) oznaczające numery punktów połączonych przez kanał. Punkt ai zawsze jest wyżej położony niż punkt bi. Zakładamy, że dwa zadane punkty połączone są bezpośrednio najwyżej jednym kanałem.

Wyjście

W jedynej linii wyjścia podana jest liczba całkowita oznaczająca ilość różnych tras spływów modulo 109.

Przykład

Wejście:
5 6
3 4
3 2
4 5
3 1
2 5
1 4

Wyjście:
11

Dodane przez:Ostry
Data dodania:2014-02-09
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.