/*
بسم الله الرحمن الرحيم
Author:
(:Muhammad Aneeq:)
*/
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <vector>
#include <iostream>
using namespace std;
int const N=2600;
int pre[N][N]={};
struct segt
{
vector<int>a;
int seg[4*N];
segt(vector<int>&s)
{
a=s;
build(1,0,a.size()-1);
}
void build(int i,int st,int en)
{
if (st==en)
{
seg[i]=a[st];
return;
}
int mid=(st+en)/2;
build(i*2,st,mid);build(i*2+1,mid+1,en);
seg[i]=max(seg[i*2],seg[i*2+1]);
}
int get(int i,int l,int r,int st,int en)
{
if (st>=l&&en<=r)
return seg[i];
if (st>r||en<l)
return 0;
int mid=(st+en)/2;
return max(get(i*2,l,r,st,mid),get(i*2+1,l,r,mid+1,en));
}
};
int getpre(int a,int b,int c,int d)
{
a++;b++;c++;d++;
return pre[c][d]-pre[c][b-1]-pre[a-1][d]+pre[a-1][b-1];
}
segt* St[2][N]={NULL};
long long count_rectangles(vector<vector<int>>a)
{
int n=a.size(),m=a[0].size();
for (int i=0;i<n;i++)
St[0][i]=new segt(a[i]);
for (int i=0;i<m;i++)
{
vector<int>z;
for (int j=0;j<n;j++)
z.push_back(a[j][i]);
St[1][i]=new segt(z);
}
bool w=0;
for (int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
if (a[i][j]>1)
w=1;
}
if (w==0)
{
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i-1][j-1];
long long ans=0;
for (int i=1;i<n-1;i++)
{
for (int j=1;j<m-1;j++)
{
if (a[i][j]==0&&a[i][j-1]==1&&a[i-1][j]==1)
{
int st=i,en=n;
while (st+1<en)
{
int mid=(st+en)/2;
if (getpre(i,j-1,mid,j)==mid-i+1&&getpre(i,j,mid,j)==0)
st=mid;
else
en=mid;
}
if (st==n-1)
continue;
int k=st;
st=j,en=m;
while (st+1<en)
{
int mid=(st+en)/2;
if (getpre(i-1,j,i,j)==(mid-j+1)&&getpre(i,j,k,mid)==0&&getpre(i,mid,k,mid+1)==(k-i+1)&&getpre(k,j,k+1,mid)==(mid-j+1))
st=mid;
else
en=mid;
}
if (st==m-1)
continue;
int l=st;
if (getpre(i,j-1,k,j)==(k-i+1)&&getpre(i-1,j,i,l)==(l-j+1)&&getpre(i,j,k,l)==0&&getpre(i,l,k,l+1)==(k-i+1)&&getpre(k,j,k+1,l)==(l-j+1))
ans++;
}
}
}
return ans;
}
long long ans=0;
for (int i=1;i<n-1;i++)
{
for (int j=1;j<m-1;j++)
{
for (int k=i;k<n-1;k++)
{
for (int l=j;l<m-1;l++)
{
bool w=0;
for (int o=i;o<=k&&!w;o++)
{
int f=St[0][o]->get(1,j,l,0,m-1);
if (f>=a[o][j-1]||f>=a[o][l+1])
w=1;
}
for (int o=j;o<=l&&!w;o++)
{
int f=St[1][o]->get(1,i,k,0,n-1);
if (f>=a[i-1][o]||f>=a[k+1][o])
w=1;
}
ans+=(!w);
}
}
}
}
return ans;
}
