#include <bits/stdc++.h>
using namespace std;
const int N = 2525;
int m, n, sum[N][N], isGood[N][N], a[N][N];
int calc(int l, int r)
{
if (l >= r - 1)
return 0;
int id = l + 1;
for (int i = l + 2; i < r; i++)
if (a[2][i] > a[2][id])
id = i;
int isGoodInterval = a[2][id] < min(a[2][l], a[2][r]) && isGood[2][r - 1] - isGood[2][l] == r - 1 - l;
return calc(l, id) + calc(id, r) + isGoodInterval;
}
long long subtask5()
{
for (int i = 2; i < m; i++)
for (int j = 2; j < n; j++)
isGood[i][j] = isGood[i][j - 1] + (a[i][j] < min(a[i - 1][j], a[i + 1][j]));
return calc(1, n);
}
int getSum(int x, int y, int xx, int yy)
{
return sum[xx][yy] + sum[x][y] - sum[xx][y] - sum[x][yy];
}
long long subtask6()
{
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
vector<int> maxCol(n + 1, 0);
long long ans = 0;
for (int i = 2; i < m; i++)
{
int maxRow = 0;
for (int j = 2; j < n; j++)
if (!a[i][j])
{
maxRow++;
maxCol[j]++;
int ii = i - maxCol[j] + 1, jj = j - maxRow + 1;
ans += getSum(ii - 1, jj - 1, i, j) == 0 &&
getSum(ii - 2, jj - 1, ii - 1, j) == maxRow &&
getSum(i, jj - 1, i + 1, j) == maxRow &&
getSum(ii - 1, jj - 2, i, jj - 1) == maxCol[j] &&
getSum(ii - 1, j, i, j + 1) == maxCol[j];
}
else maxRow = maxCol[j] = 0;
}
return ans;
}
long long count_rectangles(vector<vector<int>> _a)
{
m = _a.size();
n = _a[0].size();
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
a[i][j] = _a[i - 1][j - 1];
if (m == 3)
return subtask5();
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (a[i][j] > 1)
return 0;
return subtask6();
}
