- Time limit: 1.00 s
- Memory limit: 128 MB
Pelaat peliä, jossa on tasoa ja tehtäväsi on päästä tasolta 1 tasolle . Pelissä on myös teleporttia, joiden avulla voit liikkua tasolta toiselle. Peli on rakennettu niin, että miltään tasolta ei ole reittiä, joka palaisi samalle tasolle uudestaan.
Montako mahdollista tapaa sinulla on liikkua tasolta 1 tasolle ?
Syöte
Syötteessä on ensin kaksi kokonaislukua ja : tasojen määrä ja teleporttien määrä. Tasot on numeroitu .
Sitten syötteessä on riviä, jotka kuvaavat teleportit. Jokaisella rivillä on kaksi kokonaislukua ja . Tämä tarkoittaa, että tasolta pääsee teleportilla tasolle .
Tuloste
Tulosta yksi kokonaisluku: monellako tavalla voit läpäistä pelin. Luku voi olla suuri, joten tulosta se modulo .
Rajat
Esimerkki
Syöte:
4 5 1 2 2 4 1 3 3 4 1 4
Tuloste:
3