High hasarın boyanması#4565
Bir hasar ard-arda düzülmüş taxtadan ibarətdir. Hər bir taxta tamamilə mövcud rəngdən biri ilə rənglənməlidir. Lakin, bəzi rəng cütlükləri uyğunsuzdur və iki qonşu taxta bu uyğunsuz rənglərlə rənglənə bilməz. Belə uyğunsuz cütlük mövcuddur. Sənin vəzifən, elə rəngləmə variantlarının sayını tapmaqdır ki, heç bir iki qonşu taxta uyğunsuz rənglərlə rənglənməsin.
Məhdudiyyətlər
, və tam ədədlərdir. 1 \le N \le 10^{18}, 1 \le C \le 100, 0 \le M \le \frac{C(C+1)}{2}.
Birinci sətirdə üç tam ədəd , və verilir. Növbəti sətirin hər birində iki tam ədəd var və hər biri uyğunsuz rəng cütünü təyin edir.
Hasarı düzgün rəngləmə üsullarının sayının 10^9+7-yə bölünəndə qalanı çap edin.
Nümunə 1