---
title: Tūrista Ceļojums
---

Valstī ir $n$ pilsētas ar numuriem $1,2,\dots,n$, kuras ir savienotas ar $m$ divvirziena ceļiem. Ceļu skaits ir ne vairāk kā par $10$ lielāks, nekā pilsētu skaits. Ir iespējams tikt no jebkuras pilsētas uz jebkuru citu, izmantojot šos ceļus.

Tūrists plāno savu ceļojumu šajā valstī un ir izdomājis šādas prasības:
- ceļojums sāksies pilsētā $1$ un beigsies pilsētā $n$.
- ceļojums būs tieši $k$ soļus garš. Ar vienu soli tūrists pakustas pa vienu ceļu.
- Nav atļauts izmantot vienu ceļu divus soļus pēc kārtas. Tomēr drīkst izmantot ceļu vairākas reizes, ja starp tām ir citi soļi.

Cik daudz iespējamu ceļojumu plānu eksistē, lai aizceļotu no pilsētas $1$ uz $n$ ar $k$ soļiem? Divi plāni ir dažādi, ja kādā solī tie iet uz dažādām pilsētām.

# Ievaddati

Pirmajā rindā ir trīs veseli skaitļi $n$, $m$ un $k$: pilsētu un ceļu skaits valstī, kā arī soļu skaits tūrista ceļojumā.

Nākamās $m$ rindas apraksta ceļus. Katra rinda satur divus dažādus veselus skaitļus $u$ un $v$. Tas nozīmē, ka starp pilsētām $u$ un $v$ ir ceļš. Starp katrām divām pilsētām ir ne vairāk kā viens ceļš.

# Izvaddati

Izvadiet dažādo ceļojumu plānu skaitu. Tā kā atbilde var būt liela, izvadiet to pēc moduļa $10^9+7$.

# Ierobežojumi

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

# Piemērs 1

Ievaddati:
```
4 5 5
1 2
1 3
2 3
2 4
3 4
```

Izvaddati:
```
4
```

_Paskaidrojums_: Valsts pilsētas un ceļu struktūra ir redzama attēlā.

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

Iespējamie ceļojumu plāni ir:

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

# Piemērs 2

Ievaddati:
```
4 3 4
1 2
2 3
2 4
```

Izvaddati:
```
0
```

_Paskaidrojums_: Neeksistē ceļojuma plāns ar $4$ soļiem. Plāns $1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4$ neatbilst prasībām, jo tas izmanto ceļu starp pilsētām $2$ un $3$ divas reizes pēc kārtas.

# Vērtēšana

| Apakšuzdevums | Ierobežojumi | Punkti    |
| :-----: | ----------- | :-------: |
| 1       | $n,k \le 10$ | [score=1] |
| 2       | $n,k \le 100$ | [score=2] |
| 3       | $m=n-1$     | [score=3] |
| 4       | $m=n-1$ vai $m=n$ | [score=4] |
| 5       | $n \le 1000$ | [score=5] |
| 6       | Bez papildu ierobežojumiem | [score=6] |
