Як стало нещодавно відомо, ЗЛКШ-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.