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