---
title: Turisti teekond
---

Riigis on $n$ linna, mis on nummerdatud $1,2,\dots,n$ ning mida ühendavad $m$ kahesuunalist teed. Teede arv on ülimalt $10$ võrra suurem linnade arvust, kuid iga kahe linna vahel on võimalik liikuda, kasutades ühte või rohkemat teed. 

Turist planeerib selles riigis teekonda. Ta on otsustanud järgmist:
- Teekond algab linnas $1$ ja lõppeb linnas $n$.
- Teekond koosneb täpselt $k$ sammust, millest igaüks kulgeb mööda ühte teed.
- kahel järjestikusel sammul ei ole lubatud liikuda edasi ja tagasi mööda sama teed. Siiski on lubatud liikuda mööda sama teed, kui selle kasutamiste vahel on teisi samme.

Mitu võimalikku teekonnaplaani on kokku, et liikuda linnast $1$ linna $n$ täpselt $k$ sammuga? Kaks teekonnaplaani on erinevad, kui nad on mingil sammul erinevas linnas. 

# Sisend

Esimesel real on kolm täisarvu $n$, $m$ ja $k$: Linnade arv ja teede arv riigis ning sammude arv turisti teekonnal.

Järgmised $m$ rida kirjeldavad teid. Igal real on kaks erinevat täisarvu $u$ ja $v$, mis tähistavad, et linna $u$ ja linna $v$ vahel on tee. Iga kahe linna vahel on ülimalt üks tee.

# Väljund

Väljasta erinevate teekonnaplaanide koguarv. Kuna vastus võib olla suur, väljasta see mooduli $10^9+7$ järgi.

# Piirangud

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

# Näide 1

Sisend:
```
4 5 5
1 2
1 3
2 3
2 4
3 4
```

Väljund:
```
4
```

_Selgitus_: Riigi linnad ja teed on näha alloleval joonisel.

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

Sobivad teekonnaplaanid on:

- $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$

# Näide 2

Sisend:
```
4 3 4
1 2
2 3
2 4
```

Väljund:
```
0
```

_Selgitus_:  Pole ühtegi sobivat teekonnaplaani $4$ sammuga. Pane tähele, et plaan
$1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4$
ei sobi, sest see kasutab teed linnade $2$ ja $3$ vahel kahel järjestikusel sammul.

# Hindamine

| Grupp | Piirangud | Punktid    |
| :-----: | ----------- | :-------: |
| 1       | $n,k \le 10$ | [score=1] |
| 2       | $n,k \le 100$ | [score=2] |
| 3       | $m=n-1$     | [score=3] |
| 4       | $m=n-1$ või $m=n$ | [score=4] |
| 5       | $n \le 1000$ | [score=5] |
| 6       | Lisapiirangud puuduvad | [score=6] |
