Грандиозный праздник Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
После победы над Арчибальдом, Роланд решил провести торжественный парад. В качестве места
проведения он выбрал главную площадь и сразу же приступил к изучению ее плана. План представляет собой прямоугольное клеточное поле. Если в некотором месте на площади стоит статуя,
то соответствующая этому месту клетка на плане помечена.
На параде может быть неограниченное количество участников, каждый из которых занимает
часть площади размером 1 × 1 или 2 × 2. Разумеется, в том месте, где очередной участник будет
находиться, не должно быть статуй. Также, часть клеток может быть свободна во время праздника,
чтобы использовать их для чего-то другого.
Роланду узнать, сколько существует различных расставить участников на
площади.
Формат входных данных
В первой строке входного файла заданы три числа N, M, K — размеры площади и количество
статуй (1 ⩽ N ⩽ 6, 1 ⩽ M ⩽ 1018
, 0 ⩽ K ⩽ min(N · M, 100)).
В следующих K строках заданы позиции статуй (xi
, yi) (1 ⩽ xi ⩽ N, 1 ⩽ yi ⩽ M).
Формат выходных данных
В выходной файл выведите одно число — количество расположить участников парада
на поле. Так как это число может быть большим, выведите его остаток от деления на 109 + 9.

Dudoleyka    1   19.10.2020 20:40    3