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