Kaktus
Dərhal deyim: işlər yaxşı getmir. Dostlarla rahat bir axşam keçirmək planı daha da pis bir hala çevrildi: üzərinizə ucuz odekolonun gəzən reklamı hücum etdi və sizin üçün çox dəyərli olan argentinalı kaktus - yeganə qiymətli şey - pəncərədən atıldı.
Hadisədən dərhal sonra - ya da belə deyək, fiziki olaraq mümkün olan kimi - siz pilləkənlərlə aşağı qaçıb zərərləri qiymətləndirməyə başladınız. Və budur, sizin qiymətli kaktusunuz, sağdır! Bəzi yerlərdə cızıqlar var, amma yenə də sağdır. Bu necə baş verdi? Yumşaq bir şeyin üstünə düşdü? Sevincdən dolub-daşaraq, cavab axtarmamağa qərar verirsiniz. Mən demişdim ki, işlər pis gedir? Unut, hər şey əladır - və qeyd etməyin vaxtıdır! Əlbəttə ki, bu bayramın əsasını sizin yaşıl sancan dostunuz təşkil edəcək.
Botanika ilə az tanış olanlar üçün xatırladaq: kaktus, hər bir zirvəsi ən çox bir dövrədə yerləşən əlaqəli qrafdır. Bayram əhval-ruhiyyəsi əlavə etmək üçün, kaktusunuzun hər bir zirvəsini k rəngdən biri ilə boyamağa qərar verirsiniz. Burada özünüzə daha çox azadlıq vermək istəyirsiniz, amma kaktusların boyanmasının qızıl qaydasına riayət etmək istəyirsiniz: heç bir iki qonşu zirvə eyni rəngdə boyanmamalıdır.
Bir boyama kifayət etmir kimi görünür, buna görə də rənglər solduqdan sonra kaktusu yenidən və yenidən, hər dəfə fərqli bir boyama istifadə edərək boyamağa qərar verdiniz. Amma bunu nə qədər davam etdirə bilərsiniz? Kaktusunuzun təsvirini və k sayını bilmək, kaktusun zirvələrinin düzgün k-boyamalarının sayını hesablayın. Cavab çox böyük ola biləcəyi üçün, onu 10^9 + 7 moduluna görə qalıq olaraq hesablamaq kifayətdir.
Giriş məlumatları
Birinci sətir z testlərin sayını (1 ≤ z ≤ 50 000) ehtiva edir. Sonra testlərin təsvirləri gəlir.
Hər testin birinci sətiri üç tam ədəd n, m və k (1 ≤ n ≤ 300 000, 0 ≤ m ≤ 400 000, 2 ≤ k ≤ 10^9) - kaktusun zirvələrinin və kənarlarının sayı və rənglərin sayını ehtiva edir.
Növbəti m sətirin hər biri kaktusun kənarlarına uyğun gələn iki tam ədəd u[i], v[i] (1 ≤ u[i] ≠ v[i] ≤ n) ehtiva edir. Verilən qrafın kaktus olduğu və hər hansı iki zirvənin ən çox bir kənarla birləşdirildiyi təmin edilir.
Bütün testlərdəki zirvələrin və kənarların ümumi sayı müvafiq olaraq 3 * 10^6 və 4 * 10^6-ı keçmir.
Çıxış məlumatları
Hər test üçün bir tam ədəd çıxarın: kaktusun zirvələrinin k rənglərlə düzgün boyamalarının sayını 10^9 + 7 moduluna görə.