Берендеевы склоны
Как стало недавно известно, ЗЛКШ-2014 собираются провести на одном из лучших лыжных курортов Сочи, подготовленных в честь проведения олимпиады - на "Берендеевых склонах". Поэтому в 2014 году у лкшат появится замечательная возможность совмещать учёбу с катанием на горных лыжах и сноубордах.
Однако, владельцы лыжных курортов сочинского олимпийского комплекса не хотят пускать детей на склон за просто так. Каждому лкшонку каждый день будет выдаваться входящий в стоимость путёвки специальный пропуск -скипасс, с помощью которого он сможет зайти на склон.
Владельцы "Берендеевых склонов" не хотят, чтобы дети с помощью всего лишь одного скипасса могли кататься целый день, поэтому перестроили горнолыжный курорт следующим образом: он теперь состоит из N пунктов, на каждом из которых отдыхающий должен показать свой скипасс, и проставить дырку в нем с помощью специального компостера "КОТ-4". Если на скипассе после этого окажется более K дырок, то за лкшонком прилетает вертолет, и он отправляется в свой домик. Если же дырок окажется меньше, чем K, то он может выбрать какой-нибудь склон, ведущий из текущего пункта проверки в какой-нибудь другой и поехать по нему. Разумеется, на новом пункте проверки он снова будет должен прокомпостировать свой скипасс. Минус текущей системы в том, что отдыхающий не может покинуть склон, пока не получит свои K дырок в бейджике.., ой, скипассе.
Лкшонок Вениамин еще достаточно мал и прилежен, чтобы попасть в ЗЛКШ-2014, поэтому он хочет заранее выбрать наиболее интересные маршруты катания на "Берендеевых склонах". Но для начала ему требуется помощь -он хочет узнать, сколько же всего существует таких маршрутов. Так как это число может оказаться довольно большим, мальчик попросил Вас вывести это число по модулю 1000000007.
Помогите ему.
Входные данные
В первой строке входного файла находится три числа - N, M и K (1 ≤ N ≤ 50, 0 ≤ M ≤ 100000, 0 ≤ K≤ 1000000000) - количество проверочных пунктов, количество склонов между ними, а также количество дырок, которое лкшонок может получить в скипассе. В следующих M строках содержится информация о склонах между контрольными пунктами: в каждой строке содержатся пары чисел вида a b (1 ≤ a, b ≤ N), обозначающие наличие склона, ведущего из контрольного пункта с номером a в пункт с номером b. Все лкшата начинают свое катание по склонам с контрольного пункта номер 1 (при этом на контрольном пункте с номером 1 их пропуск не компостируется).
Выходные данные
Выведите в выходной файл единственное число P - количество маршрутов, которыми сможет прокатиться по "Берендеевым склонам" Вениамин, когда приедет в долгожданную ЗЛКШ-2014.