#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=3000;
ll pref[N][N];
ll sum(ll u, ll d, ll l, ll r){
ll ans=pref[d][r];
// cout<<ans<<endl;
if(l>0) ans-=pref[d][l-1];
// cout<<ans<<endl;
if(u>0) ans-=pref[u-1][r];
// cout<<ans<<endl;
if(l>0 && u>0) ans+=pref[u-1][l-1];
// cout<<ans<<endl;
return ans;
}
long long count_rectangles(vector<vector<int>> a){
ll n=a.size(), m=a[0].size();
pref[0][0]=a[0][0];
for(ll j=1; j<m; j++){
pref[0][j]=pref[0][j-1]+a[0][j];
}
for(ll i=1; i<n; i++){
pref[i][0]=pref[i-1][0]+a[i][0];
}
for(ll i=1; i<n; i++){
for(ll j=1; j<m; j++){
pref[i][j]=pref[i][j-1]+pref[i-1][j]-pref[i-1][j-1]+a[i][j];
}
}
ll ans=0;
for(ll u=1; u<n-1; u++){
for(ll l=1; l<m-1; l++){
if(a[u][l]==1 || a[u-1][l]==0 || a[u][l-1]==0) continue;
ll d=u;
while(d+1<n-1 && a[d+1][l]==0) d++;
ll r=l;
while(r+1<m-1 && a[u][r+1]==0) r++;
// cout<<u<<" "<<d<<" "<<l<<" "<<r<<" "<<sum(u,d,l,r)<<endl;
if(sum(u,d,l,r)==0 && sum(u-1,u-1,l,r)==r-l+1 && sum(d+1,d+1,l,r)==r-l+1 && sum(u,d,l-1,l-1)==d-u+1 && sum(u,d,r+1,r+1)==d-u+1) ans++;
}
}
return ans;
}
