eolymp
bolt
Try our new interface for solving problems
Məsələlər

Берендеевы склоны

Берендеевы склоны

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Как стало недавно известно, ЗЛКШ-2014 собираются провести на одном из лучших лыжных курортов Сочи, подготовленных в честь проведения олимпиады - на "Берендеевых склонах". Поэтому в 2014 году у лкшат появится замечательная возможность совмещать учёбу с катанием на горных лыжах и сноубордах.

Однако, владельцы лыжных курортов сочинского олимпийского комплекса не хотят пускать детей на склон за просто так. Каждому лкшонку каждый день будет выдаваться входящий в стоимость путёвки специальный пропуск -скипасс, с помощью которого он сможет зайти на склон.

Владельцы "Берендеевых склонов" не хотят, чтобы дети с помощью всего лишь одного скипасса могли кататься целый день, поэтому перестроили горнолыжный курорт следующим образом: он теперь состоит из N пунктов, на каждом из которых отдыхающий должен показать свой скипасс, и проставить дырку в нем с помощью специального компостера "КОТ-4". Если на скипассе после этого окажется более K дырок, то за лкшонком прилетает вертолет, и он отправляется в свой домик. Если же дырок окажется меньше, чем K, то он может выбрать какой-нибудь склон, ведущий из текущего пункта проверки в какой-нибудь другой и поехать по нему. Разумеется, на новом пункте проверки он снова будет должен прокомпостировать свой скипасс. Минус текущей системы в том, что отдыхающий не может покинуть склон, пока не получит свои K дырок в бейджике.., ой, скипассе.

Лкшонок Вениамин еще достаточно мал и прилежен, чтобы попасть в ЗЛКШ-2014, поэтому он хочет заранее выбрать наиболее интересные маршруты катания на "Берендеевых склонах". Но для начала ему требуется помощь -он хочет узнать, сколько же всего существует таких маршрутов. Так как это число может оказаться довольно большим, мальчик попросил Вас вывести это число по модулю 1000000007.

Помогите ему.

Giriş verilənləri

В первой строке входного файла находится три числа - N, M и K (1N50, 0M100000, 0K 1000000000) - количество проверочных пунктов, количество склонов между ними, а также количество дырок, которое лкшонок может получить в скипассе. В следующих M строках содержится информация о склонах между контрольными пунктами: в каждой строке содержатся пары чисел вида ab (1a, bN), обозначающие наличие склона, ведущего из контрольного пункта с номером a в пункт с номером b. Все лкшата начинают свое катание по склонам с контрольного пункта номер 1 (при этом на контрольном пункте с номером 1 их пропуск не компостируется).

Çıxış verilənləri

Выведите в выходной файл единственное число P - количество маршрутов, которыми сможет прокатиться по "Берендеевым склонам" Вениамин, когда приедет в долгожданную ЗЛКШ-2014.

Nümunə

Giriş verilənləri #1
3 4 2
1 2
1 3
2 3
3 1
Çıxış verilənləri #1
2
Müəllif Valentin Fondaratov