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