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