Разбиения таблицы

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

Обозначим как sum(A**i) сумму чисел в части A**i. Пусть S = sum(A1) + sum(A3) + sum(A5) + sum(A7) + sum(A9). Ваша задача — определить для заданной таблицы A число таких разбиений, что S четно.

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

0101
0101
0100

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

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

Выведите число четверок чисел (r1, r2, c1, c2), таких, что:

• 1 ≤ r1 < r2 < n;
• 1 ≤ c1 < c2 < m;
• сумма чисел в частях таблицы A с нечетными номерами четна.