---
title: Turisto kelionė
---

Šalyje yra $n$ miestų, sunumeruotų $1,2,\dots,n$, bei $m$ juos jungiančių dviejų krypčių kelių. Nors kelių yra ne daugiau kaip $10$-čia daugiau nei miestų, bet vis tiek tarp bent kurių dviejų miestų galima nukeliauti pasinaudojus vienu ar daugiau kelių.

Turistas planuoja pakeliauti po šalį vadovaudamasis šiomis taisyklėmis:
- kelionę pradės mieste $1$ ir baigs mieste $n$;
- kelionę sudarys lygiai $k$ dalių, kiekvienos jų metu bus keliaujama vienu iš kelių;
- negalima keliauti ir po to iškart grįžti tuo pačiu keliu. Kita vertus, tuo pačiu keliu galima keliauti kiek norima kartų, jei tarp kelionių tuo keliu bus važiuojama ir kitais keliais.

Kiek skirtingų kelionių galima sudaryti, kurios prasidėtų mieste $1$, baigtųsi mieste $n$ ir būtų sudarytos iš lygiai $k$ dalių? Dvi kelionės laikomos skirtingomis, jei nors vienoje iš dalių yra aplankomas skirtingas miestas.

# Pradiniai duomenys

Pirmoje eilutėje pateikti trys sveikieji skaičiai $n$, $m$ ir $k$ – miestų ir kelių skaičius bei kelionės dalių skaičius.

Kitose $m$ eilučių aprašomi keliai. Kiekvienoje eilutėje pateikta po du skirtingus sveikuosius skaičius $u$ ir $v$, kurie reiškia, kad yra kelias tarp miestų $u$ ir $v$. Tarp bent kurių miestų bus daugiausiai vienas tiesioginis kelias.

# Išvestis

Išveskite skirtingų galimų kelionių planų skaičių moduliu $10^9+7$.

# Ribojimai

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

# Pavyzdys 1

Pradiniai duomenys:
```
4 5 5
1 2
1 3
2 3
2 4
3 4
```

Išvestis:
```
4
```

_Paaiškinimas_: miestai ir keliai tarp jų yra pavaizduoti iliustracijoje žemiau.

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

Galimi kelionės planai:

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

# Pavyzdys 2

Pradiniai duomenys:
```
4 3 4
1 2
2 3
2 4
```

Išvestis:
```
0
```

_Paaiškinimas_: Negalima sudaryti kelionės iš lygiai $4$ dalių. Pastebėkite, kad šis planas
$1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4$
yra negalimas, nes kelias tarp miestų $2$ ir $3$ yra panaudotas du kartus iš eilės.

# Vertinimas

| Dalinė užduotis | Ribojimai | Taškai    |
| :-----: | ----------- | :-------: |
| 1       | $n,k \le 10$ | [score=1] |
| 2       | $n,k \le 100$ | [score=2] |
| 3       | $m=n-1$     | [score=3] |
| 4       | $m=n-1$ arba $m=n$ | [score=4] |
| 5       | $n \le 1000$ | [score=5] |
| 6       | Papildomų ribojimų nėra | [score=6] |
