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

Подарок Пятачку

Подарок Пятачку

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

Однажды Пятачок в приватной беседе рассказал Винни-Пуху, что если есть квадратик 2×2, и в каждую его клетку кладут не более одного желудя, то может получиться либо красиво, либо некрасиво. Более того, Пятачок перечислил все красивые картинки.

Через некоторое время Винни решил сделать Пятачку подарок — прямоугольник высотой m и шириной n с желудями, в котором все квадратики 2×2 — красивые. Помогите Винни-Пуху сосчитать, сколько существует различных способов сделать это.

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

В первой строке входного файла содержатся натуральные числа m и n, (2m8; 2n100). Во второй строке — натуральное число, количество красивых квадратиков. Затем идут квадратики, описание каждого — две строки, по два числа в каждой: 1 означает желудь, 0 — его отсутствие. Все квадратики различные.

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

Выведите количество прямоугольников, в которых все квадратики — хорошие. Гарантируется, что ответ не превосходит 10^9.

Пример

Входные данные #1
8 8
2
0 1
1 0
1 0
0 1
Выходные данные #1
2
Автор Михаил Дворкин
Источник Зимняя школа, Харьков 2011, День 3