#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)

using ll = long long;
using vi = vector<int>;

const int mxN = 2502;
int n, m;
int pref[mxN][mxN];

ll count_rectangles(vector<vi> a) {
	n = sz(a); m = sz(a[0]);
	ll ans = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			pref[i][j] = (j?pref[i][j-1]:0)+a[i][j];
		} 
	}
	for(int i = 1; i < n-1; i++){
		for(int j = 1; j < m-1; j++){
			if(a[i][j]) continue;
			if(!a[i][j-1] or !a[i-1][j]) continue;
			int k = j;
			while(k<m-1 and a[i-1][k+1] and !a[i][k+1]) k++;
			if(k+1>=m or !a[i][k+1]) continue;
			int l = i;
			while(l<n-1 and pref[l+1][k]==pref[l+1][j-1] and a[l+1][j-1] and a[l+1][k+1]) l++;
			if(l+1>=n or pref[l+1][k]-pref[l+1][j-1] != k-j+1) continue;
			ans++;
		}
	}
	return ans;
}