eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1.5 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

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

Ограничения

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

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
2 3 2
1 2
2 3
Çıxış verilənləri #1
5