- Time limit: 1.00 s
- Memory limit: 512 MB
Bittimaassa on kaupunkia ja niiden välillä tietä. Jokaisen kahden kaupungin välillä on jokin reitti.
Tehtäväsi on suunnitella turistikierros, joka alkaa kaupungista , kulkee teitä pitkin ja päättyy kaupunkiin . Kaksi kierrosta ovat erilaiset, jos on jokin kaupunki, jossa käyt vain toisessa kierroksista.
Montako erilaista turistikierrosta voit suunnitella?
Syöte
Syötteen ensimmäisellä rivillä on kolme kokonaislukua , ja . Kaupungit on numeroitu .
Seuraavat riviä kuvaavat tiet. Kullakin rivillä on kaksi kokonaislukua ja : kaupunkien ja välillä on tie.
Tuloste
Tulosta yksi kokonaisluku: erilaisten turistikierrosten määrä. Koska vastaus voi olla suuri, tulosta se modulo .
Esimerkki
Syöte:
7 2 5 2 7 5 7 2 1 5 3 2 6 4 5
Tuloste:
16
Osatehtävä 1 (22 pistettä)
Osatehtävä 2 (25 pistettä)
- kustakin kaupungista lähtee enintään kaksi tietä
Osatehtävä 3 (26 pistettä)
- , eli kierros alkaa ja päättyy samassa kaupungissa