Имеется забор, состоящий из \textbf{N} досок, следующих одна за другой. Требуется покрасить его таким образом, чтобы каждая доска была окрашена целиком в один из имеющихся \textbf{C} цветов. При этом некоторые пары цветов являются несовместимыми и не допускается, чтобы после покраски две соседние доски были окрашены в соответствующие цвета. Всего имеется \textbf{M} таких пар. Ваша задача -- определить количество допустимых раскрасок, то есть таких, при которых нет двух соседних досок, покрашенных в несовместимые цвета. \textbf{Ограничения} \textbf{N}, \textbf{C}, \textbf{M} --целые числа. \textbf{1} ≤ \textbf{N} ≤ \textbf{10000}, \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}.