AlgoLiga 2018

W 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 a_i oraz b_i (z zakresu od 1 do n) oznaczające numery punktów połączonych przez kanał. Punkt a_i zawsze jest wyżej położony niż punkt b_i. 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 10⁹.

Przykład

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

Wyjście:
11