22167번 - Разбиения таблицы 다국어

Рассмотрим числовую таблицу A[1..n, 1..m], заполненную нулями и единицами. Любая четверка целых чисел (r₁, r₂, c₁, c₂), такая что 1 ≤ r₁ < r₂ < n и 1 ≤ c₁ < c₂ < m, задает разбиение таблицы на девять частей, показанное на рисунке.

Обозначим как sum(A_i) сумму чисел в части A_i. Пусть S = sum(A₁) + sum(A₃) + sum(A₅) + sum(A₇) + sum(A₉). Ваша задача — определить для заданной таблицы A число таких разбиений, что S четно.

Например, для таблицы

0101
0101
0100

существует три разбиения. При (r₁=1, r₂=2, c₁=1, c₂=2) и (r₁=1, r₂=2, c₁=1, c₂=3) разбиения таковы, что сумма чисел в частях с нечетными номерами равна двум, то есть четна. При (r₁=1, r₂=2, c₁=2, c₂=3) сумма равна трем, то есть нечетна. Таким образом, подходит два разбиения.

Первая строка содержит два целых числа n и m (3 ≤ n, m ≤ 3000). Каждая из следующих n строк содержит по m символов в каждой — описание таблицы A.

Выведите число четверок чисел (r₁, r₂, c₁, c₂), таких, что:

• 1 ≤ r₁ < r₂ < n;
• 1 ≤ c₁ < c₂ < m;
• сумма чисел в частях таблицы A с нечетными номерами четна.