Körpülərin möhkəmləndirilməsi#3903
Байтlandiya hərbi təlimlərə hazırlaşır. Bu çox vacib bir tədbirdir və hətta Байтlandiyanın müdafiə naziri də təlimlərin təşkilatını şəxsən nəzarət edir. Müdafiə naziri tank təlimlərinin necə keçəcəyi ilə bağlı narahatdır.
Байтlandiya adalardan ibarətdir və bəziləri körpülərlə birləşdirilib. Hər körpü iki fərqli adanı birləşdirir və təsadüfi iki ada birbaşa olaraq bir körpüdən çox birləşdirilməyib. Байтlandiyalılar çox qənaətcil bir xalqdır, buna görə də hər adadan iki körpüdən çox çıxmır.
Tədbirin planı hələ hazır deyil, amma tank təlimlərinin planı belə olacaq: tanklar bir adadan digərinə bəzi körpülərdən istifadə edərək keçməlidirlər, hansı körpülərdən istifadə edəcəkləri vacib deyil. Байтlandiyada çoxlu körpülər var ki, illər əvvəl tikilib və tanklar üçün nəzərdə tutulmayıb. Buna görə müdafiə naziri bəzi körpüləri möhkəmləndirməyə qərar verib. Konkret olaraq, o, bəzi körpüləri elə möhkəmləndirmək istəyir ki, təlim planından asılı olmayaraq, əgər ada u-dan ada v-yə keçmək mümkün idisə, bəzi körpülər möhkəmləndirildikdən sonra ada u-dan ada v-yə möhkəmləndirilmiş körpülərlə keçmək mümkün olsun. Körpünün möhkəmləndirilməsi bahalı bir əməliyyatdır, buna görə nazir minimum sayda körpü möhkəmləndirmək istəyir.
Байтlandiyanın müdafiə naziri minimum sayda körpü möhkəmləndirməyin neçə fərqli yolu olduğunu bilmək istəyir. İki yol fərqli sayılır, əgər bir körpü bir yolda möhkəmləndirilmişsə və digər yolda möhkəmləndirilməmişsə. Müdafiə nazirinə uzun müddətdir narahat edən suala cavab tapmağa kömək edin. Cavab kifayət qədər böyük ola biləcəyi üçün onu 10^9+7 modulu ilə çıxarın.
Giriş faylının ilk sətirində iki tam ədəd n və m (1 ≤ n ≤ 10^5, 0 ≤ m ≤ 10^5) — Байтlandiyanın adalarının və körpülərinin sayı verilir.
Növbəti m sətirdə körpülər, hər biri bir sətirdə verilir. Hər bir körpü iki tam ədəd ilə verilir: v_i və u_i (1 ≤ v_i, u_i ≤ n, v_i ≠ u_i) — körpü i nömrəsi ilə birləşdirilən adaların nömrələri.
Hər bir körpünün giriş faylında bir dəfədən çox verilmədiyi təmin edilir.
Hər bir adadan iki körpüdən çox çıxmadığı təmin edilir.
Çıxış faylında körpülərin möhkəmləndirilmə yollarının sayının 10^9+7 ilə bölünməsindən alınan qalığı çıxarın.
Nümunə 1