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

Pelaat peliä, jossa on nn tasoa ja niiden välillä mm teleporttia.

Tehtäväsi on päästä tasolta 11 tasolle nn tasan kk teleportin kautta. Montako tapaa tähän on olemassa?

Syöte

Syötteen ensimmäisellä rivillä on kolme kokonaislukua nn, mm ja kk: tasojen määrä, teleporttien määrä ja askelten määrä. Tasot on numeroitu kokonaisluvuin 1,2,,n1,2,\ldots,n.

Sitten syötteessä on mm riviä, joista jokainen kuvaa yhden teleportin. Rivillä on kaksi kokonaislukua aa ja bb: teleportti vie tasolta aa tasolle bb.

Tuloste

Tulosta reittien määrä modulo 109+710^9+7.

Rajat

  • 1n1001 \le n \le 100
  • 1mn(n1)1 \le m \le n(n-1)
  • 1k1091 \le k \le 10^9
  • 1a,bn1 \le a,b \le n

Esimerkki

Syöte:

3 4 8
1 2
2 3
3 1
3 2

Tuloste:

2

Selitys: Reitit ovat 1231231231 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 3 ja 1232323231 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3.