Раскраска забора 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.