eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Раскраска забора High

Раскраска забора High

Лимит времени 2 секунды
Лимит использования памяти 256 MiB

Имеется забор, состоящий из N досок, следующих одна за другой. Требуется покрасить его таким образом, чтобы каждая доска была окрашена целиком в один из имеющихся C цветов. При этом некоторые пары цветов являются несовместимыми и не допускается, чтобы после покраски две соседние доски были окрашены в соответствующие цвета. Всего имеется M таких пар. Ваша задача – определить количество допустимых раскрасок, то есть таких, при которых нет двух соседних досок, покрашенных в несовместимые цвета.

Ограничения

N, C, M –целые числа. 1N10^18, 1C100, 0MC(C+1)/2.

Входные данные

В первой строке содержится три числа N, C, M. В каждой из последующих M строк содержится по два числа, определяющих пару несовместимых цветов.

Выходные данные

Выведите остаток от деления количества допустимых раскрасок забора на 10^9+7.

Пример

Входные данные #1
2 3 2
1 2
2 3
Выходные данные #1
5