#include "rect.h"
#include <bits/stdc++.h>

#define sz(s) ((int)s.size())

using namespace std;

const int MAX=2510;

int a[MAX][MAX];
int pref[MAX][MAX];
int l[MAX][MAX],u[MAX][MAX];

int get(int lx,int ly,int rx,int ry){
	return pref[rx][ry]-pref[rx][ly-1]-pref[lx-1][ry]+pref[lx-1][ly-1];
}

bool check(int lx,int ly,int rx,int ry){
	if(get(lx,ly,rx,ry)==0&&get(lx,ly-1,rx,ly-1)==rx-lx+1&&get(lx,ry+1,rx,ry+1)==rx-lx+1&&get(lx-1,ly,lx-1,ry)==ry-ly+1&&get(rx+1,ly,rx+1,ry)==ry-ly+1)return 1;
	return 0;
}

long long count_rectangles(vector<vector<int>> A) {
	int n=sz(A),m=sz(A[0]);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			a[i][j]=A[i-1][j-1];
			pref[i][j]=pref[i-1][j]+pref[i][j-1]+a[i][j]-pref[i-1][j-1];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]==1)l[i][j]=j;
			else l[i][j]=l[i][j-1];
			// cout<<i<<" "<<j<<" "<<a[i][j]<<" "<<l[i][j]<<"\n";
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]==1)u[i][j]=i;
			else u[i][j]=u[i-1][j];
		}
	}
	// cout<<a[2][2]<<" "<<l[2][2]<<"\n";
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[i][j]==0){
				int x=u[i][j]+1;
				int y=l[x][j]+1;
				// cout<<x<<" "<<y<<" "<<i<<" "<<j<<"\n";
				if(check(x,y,i,j))ans++;
			}
		}
	}
	return ans;
}