Muzey ekskursiya marşrutları#5436
Bu yaxınlarda unikal ziyarətçi təcrübəsi sistemi ilə prestijli interaktiv muzey açıldı. Muzeydə ekspozisiyaların ətraflı tədqiqini təşviq etmək və ziyarətçi axınını idarə etmək üçün hazırlanmış rəqəmsal buraxılış proqramı istifadə olunur.
Hər ziyarətçi girişdə xüsusi rəqəmsal muzey buraxılışı alır. Buraxılış bilet qiymətinə daxildir və elektron möhür sistemi vasitəsilə ziyarətçinin muzey boyunca irəliləyişini izləyir.
Ziyarətçilərin tələsməyib ekspozisiyalarla məna ilə qarşılıqlı əlaqədə olmasını təmin etmək üçün muzey strukturlaşdırılmış ekskursiya sistemi tətbiq etdi. Muzey N sərgi zalından ibarətdir və hər bir zalda ziyarətçilər öz rəqəmsal buraxılışlarını yoxlama stansiyasında skan etməlidirlər, bu da onların qeydlərinə rəqəmsal möhür əlavə edir. Ziyarətçi K-dan çox möhür topladıqda, avtomatik olaraq çıxışa yönləndirilir və tamamlama sertifikatı alır. Əgər K-dan az möhür varsa, cari zalından başqa zala aparan istənilən birləşdirici dəhlizi seçə və ekskursiyasına davam edə bilər. Yeni zalda o, yenidən buraxılışını skan etməlidir. Sistem tələb edir ki, ziyarətçilər buraxılışlarında tam olaraq K möhür toplayana qədər muzeydən çıxa bilməsinlər.
Gənc muzey həvəskarı Viktor öz ziyarətini planlaşdırır və muzey boyunca ən maraqlı marşrutları araşdırmaq istəyir. Ancaq əvvəlcə o, mümkün ekskursiya marşrutlarının ümumi sayını müəyyən etməlidir. Bu rəqəm kifayət qədər böyük ola biləcəyi üçün o, sizdən nəticəni 1000000007 modulu ilə hesablamağı xahiş edir.
Ona həll tapmaqda kömək edin.
Girişin birinci sətirində üç rəqəm var: N, M və K (1 ≤ N ≤ 50, 0 ≤ M ≤ 100000, 0 ≤ K ≤ 1000000000) — sərgi zallarının sayı, aralarındakı dəhlizlərin sayı və tamamlanma üçün tələb olunan möhürlərin sayı. Növbəti M sətirdə zallar arasındakı dəhlizlər təsvir edilir: hər sətir a b (1 ≤ a, b ≤ N) cütlüyünü ehtiva edir ki, bu da a zalından b zalına dəhliz olduğunu göstərir. Bütün ziyarətçilər öz ekskursiyalarına giriş zalı olan 1 nömrəli zaldan başlayırlar (bu zalda onların buraxılışı möhürlənmir).
Tək bir P rəqəmini çıxarın — Viktorun muzey boyunca keçə biləcəyi müxtəlif ekskursiya marşrutlarının sayı.
Nümunə 1