Берендеев yamacları
Yakın zamanda məlum oldu ki, ZLKŞ-2014-ü Soçidə keçirilən olimpiya şərəfinə hazırlanan ən yaxşı xizək kurortlarından biri olan "Berendey yamaclarında" keçirmək planlaşdırılır. Bu, 2014-cü ildə lkşenlər üçün təhsil ilə dağ xizəyi və snoubord sürməyi birləşdirmək üçün əla bir imkan yaradacaq.
Lakin, Soçi olimpiya kompleksinin xizək kurortlarının sahibləri uşaqları sadəcə belə yamaca buraxmaq istəmirlər. Hər lkşenə hər gün xüsusi bir keçid veriləcək, bu keçid tur paketinin qiymətinə daxildir - skipas, onun vasitəsilə o, yamaca daxil ola biləcək.
"Berendey yamaclarının" sahibləri istəmirlər ki, uşaqlar sadəcə bir skipasla bütün gün sürüşsünlər, buna görə də xizək kurortunu aşağıdakı kimi yenidən qurdular: indi o, N nöqtədən ibarətdir, hər birində istirahət edən şəxs öz skipasını göstərməli və xüsusi "KOT-4" komposteri ilə ona bir dəlik açmalıdır. Əgər skipasda bundan sonra K-dən çox dəlik olarsa, helikopter gəlib lkşeni evinə aparır. Əgər dəliklər K-dən az olarsa, o, cari yoxlama nöqtəsindən başqa birinə aparan yamacı seçib oradan sürüşə bilər. Təbii ki, yeni yoxlama nöqtəsində o, yenidən skipasını kompost etməlidir. Mövcud sistemin mənfi tərəfi odur ki, istirahət edən şəxs skipası üzərində K dəlik almayana qədər yamacı tərk edə bilmir.
Lkşen Veniamin hələ də ZLKŞ-2014-ə qatılacaq qədər kiçik və çalışqandır, buna görə də o, əvvəlcədən "Berendey yamaclarında" ən maraqlı sürüş marşrutlarını seçmək istəyir. Amma əvvəlcə ona kömək lazımdır - o, belə marşrutların sayını bilmək istəyir. Bu rəqəm kifayət qədər böyük ola biləcəyi üçün oğlan sizdən bu rəqəmi 1000000007 modulu ilə çıxarmağı xahiş etdi.
Ona kömək edin.
Giriş verilənləri
Giriş faylının ilk sətirində üç ədəd var - N, M və K (1 ≤ N ≤ 50, 0 ≤ M ≤ 100000, 0 ≤ K ≤ 1000000000) - yoxlama nöqtələrinin sayı, onların arasındakı yamacların sayı və lkşenin skipasında ala biləcəyi dəliklərin sayı. Növbəti M sətirdə nəzarət nöqtələri arasındakı yamaclar haqqında məlumat var: Hər sətirdə a b (1 ≤ a, b ≤ N) cütləri var, bu cütlər a nömrəli nəzarət nöqtəsindən b nömrəli nöqtəyə aparan yamacın mövcudluğunu göstərir. Bütün lkşenlər yamaclarda sürüşməyə 1 nömrəli nəzarət nöqtəsindən başlayırlar (bu zaman 1 nömrəli nəzarət nöqtəsində onların keçidi kompost edilmir).
Çıxış verilənləri
Çıxış faylında P tək rəqəmini göstərin - Veniaminin çoxdan gözlənilən ZLKŞ-2014-ə gəldikdə "Berendey yamaclarında" sürüşə biləcəyi marşrutların sayı.