---
title: Turistin matka
---

Maassa on $n$ kaupunkia, jotka on numeroitu $1,2,\dots,n$. Kaupunkien välillä on $m$ kaksisuuntaista tietä. Teitä on enintään $10$ enemmän kuin kaupunkeja, mutta on silti mahdollista matkustaa minkä tahansa kaupunkien välillä yhden tai useamman tien kautta.

Turisti on suunnittelemassa matkaa maassa. Hän on päättänyt seuraavasti:
- Matka alkaa kaupungista $1$ ja päättyy kaupunkiin $n$.
- Matkalla tulee olla tasan $k$ askelta, joista jokaisella kuljetaan yhtä tietä.
- Ei ole sallittua kulkea samaa tietä edestakaisin kahdella peräkkäisellä askeleella. Kuitenkin on mahdollista kulkea samaa tietä useita kertoja, jos välissä on muita askeleita.

Miten monta mahdollista matkasuunnitelmaa on kaupungista $1$ kaupunkiin $n$ tasan $k$ askeleella? Kaksi suunnitelmaa ovat erilaiset, jos jollakin askeleella siirrytään eri kaupunkiin.

# Syöte

Ensimmäisellä rivillä on kolme kokonaislukua $n$, $m$ ja $k$: maan kaupunkien ja teiden määrä sekä turistin matkan askelten määrä.

Seuraavat $m$ riviä kuvaavat tiet. Jokaisella rivillä on kaksi eri kokonaislukua $u$ ja $v$: kaupunkien $u$ ja $v$ välillä on tie. Kahden kaupungin välillä on enintään yksi tie.

# Tuloste

Tulosta erilaisten matkasuunnitelmien määrä. Koska vastaus voi olla suuri, tulosta se modulo $10^9+7$.

# Rajat

- $2 \le n \le 2 \cdot 10^5$
- $n-1 \le m \le n + 10$
- $1 \le k \le 10^4$

# Esimerkki 1

Syöte:
```
4 5 5
1 2
1 3
2 3
2 4
3 4
```

Tuloste:
```
4
```

_Selitys_: Alla oleva kuva näyttää maan kaupungit ja tiet.

![](files/example1.svg "=280x")

Mahdolliset matkasuunnitelmat ovat:

- $1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 4$
- $1 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 4$
- $1 \rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 4$
- $1 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 4$

# Esimerkki 2

Syöte:
```
4 3 4
1 2
2 3
2 4
```

Tuloste:
```
0
```

_Selitys_: Ei ole olemassa kelvollista $4$ askeleen matkasuunnitelmaa. Huomaa, että suunnitelma
$1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4$
ei ole kelvollinen, koska siinä käytetään kaupunkien $2$ ja $3$ välistä tietä kahdella peräkkäisellä askeleella.

# Pisteytys

| Osatehtävä | Rajoitukset | Pisteet    |
| :-----: | ----------- | :-------: |
| 1       | $n,k \le 10$ | [score=1] |
| 2       | $n,k \le 100$ | [score=2] |
| 3       | $m=n-1$     | [score=3] |
| 4       | $m=n-1$ tai $m=n$ | [score=4] |
| 5       | $n \le 1000$ | [score=5] |
| 6       | Ei lisärajoituksia | [score=6] |
