Statement is not available in English language
B. Выигрыш
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Снежка заняла первое место на конкурсе красоты в городе Мышкин, и получила приз от спонсора соревнований, авиакомпании Ковёр-Самолет, — путешествие самолетами компании.

Авиакомпания Ковёр-Самолет соединяет авиарейсами некоторые пары из $$$N$$$ аэропортов (будем называть аэропорты $$$1$$$, $$$2$$$, $$$\dots$$$, $$$N$$$). Город Мышкин (а именно там живет Снежка) находится возле аэропорта номер $$$1$$$. Снежка имеет право совершить ровно $$$K$$$ перелетов — таков приз. При этом она начинает путешествие в аэропорту $$$1$$$, и хочет закончить путешествие там же.

Требуется определить, сколько существует способов организовать путешествие. Заметим, что Снежка может посещать какие-то аэропорты (в том числе и первый) многократно. Важно только, чтобы путешествие заканчивалось в $$$1$$$. Путешествия, отличающиеся порядком посещения аэропортов, считаются различными.

Входные данные

В первой строке находятся через пробел три целых числа $$$N$$$, $$$M$$$ и $$$K$$$ $$$(2 \le N \le 100; 1 \le M \le \frac{N \cdot (N - 1)}{2}; 1 \le K \le 60)$$$ — количество аэропортов, количество различных авиарейсов компании и количество перелетов в маршруте Снежки соответственно.

Каждая из следующих $$$M$$$ строк содержит через пробел два целых числа $$$A$$$ и $$$B$$$ $$$(1 \le A, B \le N; A \ne B)$$$ — конечные пункты одного авиарейса. Все авиарейсы – двусторонние, т.е. пара $$$A$$$ $$$B$$$ означает, что есть авиарейсы и из $$$A$$$ в $$$B$$$, и из $$$B$$$ в $$$A$$$.

Гарантируется, что все рейсы указаны не более одного раза.

Выходные данные

Вывести одно целое число — количество способов, которыми Снежка может организовать свое путешествие. Гарантируется, что результат не превосходит $$$2 \cdot 10^9$$$.

Примеры
Входные данные
4 4 4
1 2
1 3
2 4
3 4
Выходные данные
8
Входные данные
4 4 3
1 2
1 3
2 4
3 4
Выходные данные
0
Примечание

Все возможные маршруты в примере $$$1$$$:

1-2-4-2-1, 1-2-4-3-1

1-3-4-2-1, 1-3-4-3-1

1-2-1-2-1, 1-3-1-2-1

1-2-1-3-1, 1-3-1-3-1