Autosacīkstēs piedalās N automašīnas, kas sanumurētas ar naturāliem skaitļiem no 1 līdz N pēc kārtas. Automašīnas pa šauru ceļu joņo viena aiz otras, veikdamas apdzīšanas retajās vietās, kur tas ir iespējams. “Apdzīšana” nozīmē, ka viena automašīna, kas atradās tieši aiz citas, aizbrauca tai garām - katras apdzīšanas rezultātā tieši divas blakus mašīnas samainās vietām.

Ferdinands ir nokavējis sacīkšu sākumu un tagad ar interesi seko sacīkstēm, pierakstot visas apdzīšanas pēc kārtas. Kāda ir bijusi automašīnu secība, pirms Ferdinands sācis veikt pierakstus, nav zināms.

Piemēram, ja N=4, 1. auto apdzinis 4. un 2. auto apdzinis 4., tad iespējamās divas automašīnu secības pēc šīm apdzīšanām ir 

Diemžēl, savos pierakstos Ferdinands var būt kļūdījies un kādu apdzīšanu izlaidis vai ierakstījis nepareizi.

Piemēram, ja N=5 un ierakstīts, ka 2. auto apdzinis 3. un 3. auto apdzinis 4., tad šīs apdzīšanas nevar sekot tieši viena aiz otras -- pēc pirmās apdzīšanas 3. auto atrodas tieši aiz 2. auto un nevar apdzīt 4. auto. Tātad šajā gadījumā nav iespējama neviena automašīnu secība.

Uzrakstiet programmu, kas aprēķina dažādo iespējamo automašīnu secību pēc Ferdinanda novērotajām apdzīšanām!

Ievaddatu pirmajā rindā dotas naturālu skaitļu N (automašīnu skaits, N ≤ 10⁵) un A (pierakstīto apdzīšanu skaits, A ≤ 10⁵) vērtības, kas atdalītas ar tukšumzīmi. Ievaddatu nākamajās A rindās doti apdzīšanu apraksti tādā secībā, kā tās pierakstījis Ferdinands. Katru apdzīšanu apraksta divi atšķirīgi naturāli skaitļi robežās no 1 līdz N, kas atdalīti ar tukšumzīmi. Pirmais skaitlis ir tās automašīnas numurs, kas veica apdzīšanu, bet otrais - tās mašīnas numurs, kas tika apdzīta.

Vienīgajā rindā jāizvada vesels nenegatīvs skaitlis - dažādo iespējamo automašīnu secību pēc Ferdinanda novērotajām apdzīšanām skaits pēc moduļa 10⁹+9.

Uzdevums no Latvijas 31. Informātikas olimpiādes.