---
title: Подорож туриста
---

Країна з $n$ містами, пронумерованими $1,2,\dots,n$, з'єднана $m$ двосторонніми дорогами. Доріг щонайбільше на $10$ більше, ніж міст, але між будь-якими двома містами існує шлях, використовуючи одну або більше доріг.

Турист планує подорож країною. Він вирішив що:
- Подорож починається у місті $1$ і закінчується у місті $n$.
- Подорож має складатися рівно з $k$ кроків, кожен з яких — проїзд однією дорогою.
- Не дозволяється повертатися тією самою дорогою одразу на наступному кроці. Однак можна проїжджати тією самою дорогою кілька разів, якщо між цими проїздами є інші кроки.

Скільки існує можливих планів подорожі з міста $1$ до міста $n$ за $k$ кроків? Два плани вважаються різними, якщо на якомусь кроці вони проходять через різні міста.

# Вхідні дані

Перший рядок містить три цілі числа $n$, $m$ і $k$: кількість міст і доріг у країні, а також кількість кроків у подорожі туриста.

Наступні $m$ рядків описують дороги. Кожен рядок містить два різні цілі числа $u$ і $v$, що означає, що між містами $u$ і $v$ є дорога. Між двома містами є щонайбільше одна дорога.

# Вихідні дані

Виведіть кількість різних планів подорожі. Оскільки відповідь може бути великою, виведіть її за модулем $10^9+7$.

# Обмеження

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

# Приклад 1

Вхідні дані:
```
4 5 5
1 2
1 3
2 3
2 4
3 4
```

Вихідні дані:
```
4
```

_Пояснення_: Міста та дороги країни зображені на рисунку нижче.

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

Можливі плани подорожі:

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

# Приклад 2

Вхідні дані:
```
4 3 4
1 2
2 3
2 4
```

Вихідні дані:
```
0
```

_Пояснення_: Не існує допустимого плану подорожі з $4$ кроками. Зверніть увагу, що план
$1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4$
є недопустимим, оскільки він використовує дорогу між містами $2$ і $3$ у два послідовні кроки.

# Оцінювання

| Підзадача | Обмеження | Бали    |
| :-----: | ----------- | :-------: |
| 1       | $n,k \le 10$ | [score=1] |
| 2       | $n,k \le 100$ | [score=2] |
| 3       | $m=n-1$     | [score=3] |
| 4       | $m=n-1$ або $m=n$ | [score=4] |
| 5       | $n \le 1000$ | [score=5] |
| 6       | Без додаткових обмежень | [score=6] |
