Junior üçün hasarın rənglənməsi#4566
Bir hasar ardıcıll düzülmüş taxtadan ibarətdir. Hər taxta tamamilə mövcud rəngdən biri ilə rənglənməlidir. Lakin bəzi rəng cütləri uyğun deyil, yəni iki qonşu taxta bu rənglərlə rənglənə bilməz. Belə uyğun olmayan cüt mövcuddur. Sizin vəzifəniz hasarı elə rəngləməyin neçə müxtəlif yolu olduğunu hesablamaqdır ki, heç bir iki qonşu taxta uyğun olmayan rənglərlə rənglənməsin.
Məhdudiyyətlər
, , tam ədədlərdir. 1 \leq N \leq 10000, 1 \leq C \leq 100, 0 \leq M \leq \frac{C(C+1)}{2}.
Birinci sətrdə üç tam ədəd var: , , . Növbəti sətrin hər birində iki tam ədəd verilir, uyğun olmayan iki rəngin nömrəsi.
Hasarın düzgün rənglənmə üsullarının sayını 10^9 + 7-yə bölünmədən qalanı çap edin.
Nümunə 1