---
title: Podróż turysty
---

W Bajtocji znajduje się $n$ miast ponumerowanych $1, 2, \dots, n$, połączonych $m$ dwukierunkowymi drogami. Liczba dróg jest większa od liczby miast o co najwyżej $10$, ale wciąż możliwe jest przemieszczenie się między dowolnymi dwoma miastami za pomocą jednej lub większej liczby dróg.

Pewien turysta planuje podróż po Bajtocji. Ustalił on następujące zasady:
- Podróż rozpocznie się w mieście $1$, a zakończy w mieście $n$.
- Podróż musi składać się z dokładnie $k$ kroków, gdzie każdy krok to przejazd jedną drogą.
- Zabronione jest przejeżdżanie tą samą drogą tam i z powrotem w dwóch kolejnych krokach. Możliwe jest jednak wielokrotne przejechanie tej samej drogi, jeśli kroki te są oddzielone innymi drogami.

Ile istnieje możliwych planów podróży z miasta $1$ do miasta $n$ w dokładnie $k$ krokach? Dwa plany uznajemy za różne, jeśli w dowolnym kroku turysta znajdzie się w innym mieście.

# Wejście

Pierwszy wiersz zawiera trzy liczby całkowite $n, m$ oraz $k$: liczbę miast, liczbę dróg oraz liczbę kroków w podróży turysty.

Kolejne $m$ wierszy opisuje drogi. Każdy wiersz zawiera dwie różne liczby całkowite $u$ oraz $v$, oznaczające drogę łączącą miasto $u$ z miastem $v$. Pomiędzy dwoma miastami istnieje co najwyżej jedna droga.

# Wyjście

Wypisz liczbę różnych planów podróży. Ponieważ wynik może być bardzo duży, wypisz go modulo $10^9+7$.

# Ograniczenia

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

# Przykład 1

Wejście:
```
4 5 5
1 2
1 3
2 3
2 4
3 4
```

Wyjście:
```
4
```

_Wyjaśnienie_: Miasta i drogi w państwie przedstawiono na poniższym rysunku.


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

Możliwe plany podróży to:

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

# Przykład 2

Wejście:
```
4 3 4
1 2
2 3
2 4
```

Wyjście:
```
0
```

_Wyjaśnienie_: Nie istnieje żaden poprawny plan podróży składający się z $4$ kroków. Zauważ, że plan
$1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4$
jest niepoprawny, ponieważ wykorzystuje drogę między miastami $2$ i $3$ w dwóch kolejnych krokach.

# Ocenianie

| Podzadanie | Ograniczenia | Punkty    |
| :-----: | ----------- | :-------: |
| 1       | $n,k \le 10$ | [score=1] |
| 2       | $n,k \le 100$ | [score=2] |
| 3       | $m=n-1$     | [score=3] |
| 4       | $m=n-1$ lub $m=n$ | [score=4] |
| 5       | $n \le 1000$ | [score=5] |
| 6       | Brak dodatkowych ograniczeń | [score=6] |
