#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
#define ll long long
#define pb push_back
#define en '\n'
#define all(v) v.begin(),v.end()
#define pii pair <int,int>
#define f first
#define s second
#define mp make_pair
const int N = 2600;
int a[N][N],n,m,pr[N][N];
int calc(int lx,int rx,int ly,int ry) {
if(lx > rx || ly > ry)return 0;
return pr[rx][ry] - pr[rx][ly - 1] - pr[lx - 1][ry] + pr[lx - 1][ly - 1];
}
bool check(int lx,int rx,int ly,int ry) {
if(calc(lx + 1,rx - 1,ly + 1,ry - 1))return 0;
if(calc(lx,rx,ly,ly) != rx - lx + 1 || calc(lx,rx,ry,ry) != rx - lx + 1)return 0;
if(calc(lx,lx,ly,ry) != ry - ly + 1 || calc(rx,rx,ly,ry) != ry - ly + 1)return 0;
return 1;
}
int firh(int x,int y) {
int l = x + 1,r = n,ans = n + 5;
while(l <= r) {
int mid = (l + r) / 2;
if(calc(x + 1,mid,y,y)) {
ans = mid;
r = mid - 1;
}else {
l = mid + 1;
}
}
return ans;
}
int firg(int x,int y) {
int l = y + 1,r = m,ans = m + 5;
while(l <= r) {
int mid = (l + r) / 2;
if(calc(x,x,y + 1,mid)) {
ans = mid;
r = mid - 1;
}else {
l = mid + 1;
}
}
return ans;
}
ll count_rectangles(vector<vector<int> > A) {
n = A.size();
m = A[0].size();
for(int i = 0;i < n;i++) {
for(int j = 0;j < m;j++) {
a[i + 1][j + 1] = A[i][j];
}
}
for(int i = 1;i <= n;i++) {
int tek = 0;
for(int j = 1;j <= m;j++) {
tek += a[i][j];
pr[i][j] = pr[i - 1][j] + tek;
}
}
ll ans = 0;
for(int i = 1;i < n - 1;i++) {
for(int j = 1;j < m - 1;j++) {
int fx = firh(i,j + 1),fy = firg(i + 1,j);
ans += check(i,fx,j,fy);
}
}
return ans;
}
