---
title: Tourismus
---

Ein Land mit $n$ Städten, die mit $1, 2, \dots, n$ nummeriert sind, ist durch $m$ beidseitig befahrbare Straßen verbunden. Es gibt höchstens $10$ Straßen mehr als die Anzahl der Städte, aber es ist dennoch möglich, zwischen zwei beliebigen Städten über eine oder mehrere Straßen zu reisen. 

Ein Tourist plant eine Reise durch das Land. Er hat Folgendes beschlossen:
- Die Reise beginnt in Stadt $1$ und endet in Stadt $n$.
- Die Reise soll aus genau $k$ Etappen bestehen, wobei jede Etappe einer Straße entspricht.
- Es ist nicht erlaubt, in zwei aufeinanderfolgenden Etappen dieselbe Straße hin und zurück zu befahren. Es ist jedoch möglich, dieselbe Straße mehrmals zu befahren, wenn dazwischen andere Etappen liegen.

Wie viele mögliche Reisepläne gibt es, um in $k$ Etappen von Stadt $1$ nach Stadt $n$ zu gelangen? Zwei Pläne unterscheiden sich, wenn sie in irgendeiner Etappe unterschiedliche Städte ansteuern.

# Eingabe

Die erste Zeile enthält drei ganze Zahlen $n$, $m$ und $k$: die Anzahl der Städte und Straßen im Land sowie die Anzahl der Etappen auf der Reise des Touristen.

Die folgenden $m$ Zeilen beschreiben die Straßen. Jede Zeile enthält zwei unterschiedliche ganze Zahlen $u$ und $v$, was bedeutet, dass es eine Straße zwischen Stadt $u$ und Stadt $v$ gibt. Zwischen zwei Städten gibt es höchstens eine Straße.

# Ausgabe

Gib die Anzahl der verschiedenen Reiserouten aus. Da die Antwort sehr groß sein kann, gib sie modulo $10^9+7$ aus.

# Beschränkungen

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

# Beispiel 1

Eingabe:
```
4 5 5
1 2
1 3
2 3
2 4
3 4
```

Ausgabe:
```
4
```

_Erklärung_: Die Städte und Straßen des Landes sind in der folgenden Abbildung dargestellt.

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

Die möglichen Reisepläne sind:

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

# Beispiel 2

Eingabe:
```
4 3 4
1 2
2 3
2 4
```

Ausgabe:
```
0
```

_Erklärung_: Es gibt keinen gültigen Reiseplan mit 4 Etappen. Beachte, dass der Plan
$1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4$
ungültig ist, da er die Straße zwischen den Städten $2$ und $3$ in zwei aufeinanderfolgenden Etappen nutzt.

# Bewertung

| Teilaufgabe | Beschränkungen | Punkte |
| :-----: | ----------- | :-------: |
| 1       | $n,k \le 10$ | [score=1] |
| 2       | $n,k \le 100$ | [score=2] |
| 3       | $m=n-1$     | [score=3] |
| 4       | $m=n-1$ oder $m=n$ | [score=4] |
| 5       | $n \le 1000$ | [score=5] |
| 6       | Keine zusätzlichen Beschränkungen | [score=6] |
