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