Шахове поле

Панночка Анночка нещодавно потрапила на співбесіду в ІТ-компанію. На цій співбесіді їй дали дуже цікаву задачу:

Дівчині дана площина, поділена на одиничні квадрати. Тобто такі, що кожна їхня сторона дорівнює $1$. При чому кожний квадрат пофарбований або у білий, або у чорний колір.

Назвемо площину шаховою з параметрами $n$ і $m$, якщо вона складається з прямокутників, що мають $n$ одиниць у висоту та $m$ одиниць у ширину. Також всі ці прямокутники мають бути пофарбовані або у білий колір, або у чорний. При чому кожен білий прямокутник межує лише з чорними та навпаки "— кожен чорний межує тільки з білими.

Наприклад, наступні площини є шаховими з параметрами $2$ і $3$ (синім зображено вісі координат):

А оці не є:

Як ви вже могли помітити, дуже часто шахових площин з параметрами $n$ і $m$ буває чимало. Задача полягає в тому, щоб сказати, скільки таких є. Ні-і-і-і, це надто легко.

Анночці також дали $k$ квадратів на цій площині та їхні кольори. Паночка має знайти кількість шахових площин з параметрами $n$ і $m$ таких, що квадрати з відповідними координатами мають задані кольори. Допоможіть їй зробити це!

Більш формально, вам дано $k$ трійок чисел: x_i, y_i, c_i, де (x_i,y_i) — координати лівого нижнього краю квадрата, а c_i дорівнює $0$, якщо цей квадрат має бути пофарбований у чорний колір, і дорівнює $1$, якщо цей квадрат має бути пофарбований у білий колір. Потрібно вивести кількість різних шахових площин з параметрами $n$ і $m$, які підходять під ці обмеження. Дві шахові площини вважаються різними, якщо існує хоч один квадрат, що пофарбований у різні кольори на цих площинах.

Примітка

Зліва зображення єдиної площини, яка підходить під обмеження прикладу $1$.

Справа "— одна з можливих $8$ площин, які задовольняють умови прикладу $2$.

(Синім позначено осі координат, світло-сірим "— квадратики, які за умовою мають бути білими, темно-сірим "— квадратики, які за умовою мають бути чорними).