Разфарбування огорожі High
Є огорожа, що складається з N дощок, які йдуть одна за одною. Потрібно пофарбувати його таким чином, щоб кожна дошка була пофарбована повністю у один з наявних C кольорів. При цьому деякі пари кольорів є несумісними и не допускається, щоб після пофарбування дві сусіднні дошки були пофарбовані у відповідні кольори. Усього є M таких пар. Ваша задача – визначити кількість допустимих розфарбувань, тобто таких, при яких немає двох сусідніх дощок, пофарбованих у несуміні кольори.
Обмеження
N, C, M –цілі числа. 1 ≤ N ≤ 10^18, 1 ≤ C ≤ 100, 0 ≤ M ≤ C(C+1)/2.
Вхідні дані
У першому рядку міститься три числа N, C, M. У кожному з наступних M рядків містиьтся по два числа, які визначають пару несуміних кольорів.
Вихідні дані
Виведіть залишок від ділення кількості допустимих розфарбувань огорожі на 10^9+7.