Fișierul intrare/ieșire	coborare.in, coborare.out	Sursă	ad-hoc
Autor	clasică	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.15 sec	Limită de memorie	8192 KB
Scorul tău	N/A	Dificultate	2.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Coborâre (clasele 11-12)

Un turist a făcut o excursie până în vârful unui munte. Acum, el dorește să coboare înapoi la cabană. Muntele este presărat cu poiene între care se află cărări. Fiecare cărare leagă două poiene diferite, iar într-o poiană pot ajunge mai multe cărări. Turistul se întreabă: câte trasee diferite există din vârful muntelui la cabană, care să meargă numai pe cărări și numai la vale?

Date de intrare

Fișierul de intrare coborare.in conține pe prima linie două numere N M, unde N este numărul de poiene, iar M este numărul de cărări. Pe următoarele M linii se află câte o pereche de numere x y, cu semnificația că există o cărare care coboară din poiana x în poiana y.

Date de ieșire

În fișierul de ieșire coborare.out se va scrie un singur număr, respectiv numărul de trasee distincte modulo 100003.

Restricții

• 1 ≤ N ≤ 100.000
• 1 ≤ M ≤ 300.000
• Poienele au numere între 1 și N.

Exemplu

Explicație

...