Розфарбування огорожі Junior#4566
Є паркан, що складається з дощок, розташованих у ряд. Кожну дошку потрібно повністю пофарбувати в один з доступних кольорів. Однак деякі пари кольорів несумісні, тобто дві сусідні дошки не можна фарбувати в ці кольори. Є таких несумісних пар. Ваше завдання — обчислити кількість способів легально пофарбувати паркан так, щоб жодні дві сусідні дошки не були пофарбовані в несумісні кольори.
Обмеження
, , — цілі числа. 1 \leq N \leq 10000, 1 \leq C \leq 100, 0 \leq M \leq \frac{C(C+1)}{2}.
Перший рядок містить три цілі числа: , , . Кожен з наступних рядків містить по два цілі числа, що задають пару несумісних кольорів.
Виведіть остачу від ділення кількості можливих за правилами розфарбувань паркану на 10^9 + 7.
Приклад 1