CSES - Teleportit
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Pelaat peliä, jossa on nn tasoa ja tehtäväsi on päästä tasolta 1 tasolle nn. Pelissä on myös mm 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 nn?

Syöte

Syötteessä on ensin kaksi kokonaislukua nn ja mm: tasojen määrä ja teleporttien määrä. Tasot on numeroitu 1,2,,n1,2,\ldots,n.

Sitten syötteessä on mm riviä, jotka kuvaavat teleportit. Jokaisella rivillä on kaksi kokonaislukua aa ja bb. Tämä tarkoittaa, että tasolta aa pääsee teleportilla tasolle bb.

Tuloste

Tulosta yksi kokonaisluku: monellako tavalla voit läpäistä pelin. Luku voi olla suuri, joten tulosta se modulo 109+710^9+7.

Rajat

  • 1n1051 \le n \le 10^5
  • 1m21051 \le m \le 2 \cdot 10^5
  • 1a,bn1 \le a,b \le n

Esimerkki

Syöte:

4 5
1 2
2 4
1 3
3 4
1 4

Tuloste:

3