---
title: Ferðalag ferðamannsins
---

Land með $n$ borgum númeraðar $1,2,\dots,n$ er tengd með $m$ tvístefndum vegum. Það eru að mestu lagi $10$ sinnum fleiri vegir en fjöldi borga, það er hinsvegar ennþá hægt að ferðast milli tveggja borga með því að nota einn eða fleiri vegi.

Ferðamaður er að plana ferðalag í landinu. Hann hefur ákveðið eftirfarandi:
- Ferðin mun hefjast í borg $1$ og enda í borg $n$.
- Ferðin verður að innihalda nákvæmlega $k$ skref, hvert þeirra að ferðast yfir einn veg.
- Það er ekki leyfilegt að ferðast fram og til baka yfir sama vegin í tveimur skrefum í röð. Hinsvegar má ferðast yfir sama vegin tvisvar ef það eru önnur skref á milli.

Hversu mörg möguleg ferðalög er til þar sem ferðast er frá borg $1$ til borg $n$ í $k$ skrefum? Tvö ferðalög eru mismunandi ef þau heimsækja mismunandi borgir í einhverju skrefi.

# Inntak

Fyrsta línan inniheldur þrjár heiltölur, $n$, $m$ og $k$: fjöldi borga og fjölda vega í landinu, auk þess fjöldi skrefa í ferðalagi ferðamannsins.

Næstu $m$ línur eftir það lýsa vegunum. Hver lína inniheldur tvær ólíkar heiltölur $u$ og $v$, sem þýðir að það er vegur milli borg $u$ og borg $v$. Það eru í mesta lagi einn vegur milli tveggja borga.

# Úttak

Prentaðu fjölda mismunadi ferðalaga. Þar sem svarið getur verið stórt skal prenta það mátað við $10^9+7$.

# Takmarkanir

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

# Dæmi 1

Inntak:
```
4 5 5
1 2
1 3
2 3
2 4
3 4
```

Úttak:
```
4
```

_Útskýring_: Borgirnar og vegirnir í landinu eru sýndir í skýringarmyndinni fyrir neðan.

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

Mögulegu ferðalögin eru:

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

# Dæmi 2

Inntak:
```
4 3 4
1 2
2 3
2 4
```

Úttak:
```
0
```

_Útskýring_: Það er ekkert gilt ferðalag með $4$ skref. Athugið
að planið $1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4$
er ógilt þar sem það notar leiðina á milli borganna $2$ og $3$ í tveimur skrefum í röð.

# Stigagjöf

| Hópur   | Takmarkanir | Stig      |
| :-----: | ----------- | :-------: |
| 1       | $n,k \le 10$ | [score=1] |
| 2       | $n,k \le 100$ | [score=2] |
| 3       | $m=n-1$     | [score=3] |
| 4       | $m=n-1$ or $m=n$ | [score=4] |
| 5       | $n \le 1000$ | [score=5] |
| 6       | Engar frekari takmarkanir | [score=6] |
