Подарок Пятачку
Однажды Пятачок в приватной беседе рассказал Винни-Пуху, что если есть квадратик 2×2, и в каждую его клетку кладут не более одного желудя, то может получиться либо красиво, либо некрасиво. Более того, Пятачок перечислил все красивые картинки.
Через некоторое время Винни решил сделать Пятачку подарок — прямоугольник высотой m и шириной n с желудями, в котором все квадратики 2×2 — красивые. Помогите Винни-Пуху сосчитать, сколько существует различных способов сделать это.
Входные данные
В первой строке входного файла содержатся натуральные числа m и n, (2 ≤ m ≤ 8; 2 ≤ n ≤ 100). Во второй строке — натуральное число, количество красивых квадратиков. Затем идут квадратики, описание каждого — две строки, по два числа в каждой: 1 означает желудь, 0 — его отсутствие. Все квадратики различные.
Выходные данные
Выведите количество прямоугольников, в которых все квадратики — хорошие. Гарантируется, что ответ не превосходит 10^9.