Given a rows * columns matrix mat of ones and zeros, return how many submatrices have all ones.
 
Example 1:
Input: mat = [[1,0,1],
              [1,1,0],
              [1,1,0]]
Output: 13
Explanation:
There are 6 rectangles of side 1x1.
There are 2 rectangles of side 1x2.
There are 3 rectangles of side 2x1.
There is 1 rectangle of side 2x2. 
There is 1 rectangle of side 3x1.
Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.

Example 2:
Input: mat = [[0,1,1,0],
              [0,1,1,1],
              [1,1,1,0]]
Output: 24
Explanation:
There are 8 rectangles of side 1x1.
There are 5 rectangles of side 1x2.
There are 2 rectangles of side 1x3. 
There are 4 rectangles of side 2x1.
There are 2 rectangles of side 2x2. 
There are 2 rectangles of side 3x1. 
There is 1 rectangle of side 3x2. 
Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.

Example 3:
Input: mat = [[1,1,1,1,1,1]]
Output: 21

Example 4:
Input: mat = [[1,0,1],[0,1,0],[1,0,1]]
Output: 5

 
Constraints:

1 <= rows <= 150
1 <= columns <= 150
0 <= mat[i][j] <= 1

Difficulty: MEDIUM
Tags: Matrices

Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures

Starter code:
class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        

Solutions:
class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(n, m) = (len(mat), len(mat[0]))
		heights = [0] * m
		res = 0
		for i in range(0, n):
			stack = []
			count = 0
			for j in range(0, m):
				if mat[i][j] == 1:
					heights[j] += 1
				else:
					heights[j] = 0
			for (index, height) in enumerate(heights):
				while stack and height < heights[stack[-1]]:
					curr = stack.pop()
					left = stack[-1] if stack else -1
					count -= (heights[curr] - height) * (curr - left)
				count += height
				res += count
				stack.append(index)
		return res


class Solution:

	def numSubmat(self, matrix):
		(m, n) = (len(matrix), len(matrix[0]))
		res = 0
		heights = [0] * (n + 1)
		for x in range(m):
			stack = []
			dp = [0] * (n + 1)
			for y in range(n):
				if matrix[x][y] == 1:
					heights[y] = heights[y] + 1
				else:
					heights[y] = 0
			for right in range(n + 1):
				while stack and heights[right] <= heights[stack[-1]]:
					cur = stack.pop()
				if stack:
					left = stack[-1]
					dp[right] = dp[left] + heights[right] * (right - left)
				else:
					left = -1
					dp[right] = heights[right] * (right - left)
				stack.append(right)
			res += sum(dp)
		return res


class Solution:

	def numSubmat(self, mat):
		if not mat:
			return 0
		for i in range(len(mat)):
			for j in range(1, len(mat[0])):
				mat[i][j] = 1 + mat[i][j - 1] if mat[i][j] != 0 else 0
		for j in range(len(mat[0])):
			stack = [(-1, -1)]
			for i in range(len(mat)):
				while stack and mat[i][j] < stack[-1][1]:
					stack.pop()
				stack.append((i, mat[i][j]))
				mat[i][j] = mat[i][j] * (i - stack[-2][0]) + (mat[stack[-2][0]][j] if stack[-2][0] != -1 else 0)
		return sum([sum(arr) for arr in mat])


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		row = len(mat)
		col = len(mat[0])
		for j in range(col):
			for i in range(1, row):
				mat[i][j] = mat[i - 1][j] + 1 if mat[i][j] == 1 else 0
		total = 0
		for i in range(row):
			for j in range(col):
				if mat[i][j] == 0:
					continue
				cur = j
				delta = 0
				min_h = float('inf')
				while cur >= 0 and mat[i][cur] != 0:
					cur_h_above = mat[i - 1][cur] if i - 1 >= 0 else 0
					min_h = min(min_h, cur_h_above)
					delta += min_h + 1
					cur -= 1
				total += delta
		return total


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		rows = len(mat)
		columns = len(mat[0])

		def countSubmat(s_r, s_c):
			e_r = rows
			e_c = columns
			c_r = s_r
			c_c = s_c
			count = 0
			while c_r < e_r:
				if mat[c_r][s_c] == 0:
					break
				else:
					count += 1
					c_c = s_c + 1
				while c_c < e_c:
					if mat[c_r][c_c] == 1:
						count += 1
					else:
						e_c = c_c
					c_c += 1
				c_r += 1
				c_c = s_c
			return count
		res = 0
		for i in range(rows):
			for j in range(columns):
				res += countSubmat(i, j)
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		if not mat:
			return 0
		(m, n) = (len(mat), len(mat[0]))
		prefix = [[0] * n for _ in range(m)]
		for i in range(m):
			for j in range(n - 1, -1, -1):
				if j == n - 1:
					prefix[i][j] = mat[i][j]
				if mat[i][j] == 0:
					continue
				if j + 1 <= n - 1:
					prefix[i][j] = prefix[i][j + 1] + mat[i][j]
		print(prefix)
		count = [[0] * n for _ in range(m)]
		for i in range(m):
			for j in range(n):
				width = prefix[i][j]
				res = width
				for k in range(i + 1, m):
					if prefix[k][j] <= width:
						width = prefix[k][j]
						res += prefix[k][j]
					else:
						res += width
				count[i][j] = res
		print(count)
		ans = 0
		for i in range(m):
			ans += sum(count[i])
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		res = 0
		(m, n) = (len(mat), len(mat[0]))
		dp = [[0 for j in range(n)] for i in range(m)]
		for i in range(m):
			for j in range(n):
				if mat[i][j]:
					if j == 0:
						dp[i][j] = 1
					else:
						dp[i][j] = dp[i][j - 1] + 1
		for i in range(m):
			for j in range(n):
				if mat[i][j] == 0:
					continue
				(row, minwidth) = (i, float('inf'))
				while row >= 0 and mat[row][j]:
					minwidth = min(minwidth, dp[row][j])
					res += minwidth
					row -= 1
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(R, C) = (len(mat), len(mat[0]))
		hist = [[0] * C for _ in range(R)]
		for r in range(R):
			for c in range(C):
				if mat[r][c]:
					hist[r][c] = 1 if r == 0 else hist[r - 1][c] + 1
		ret = 0
		for row in hist:
			all_stacks = []
			stack = []
			for num in row:
				if num > 0:
					stack.append(num)
				elif stack:
					all_stacks.append(stack[:])
					stack = []
			if stack:
				all_stacks.append(stack)
			for stack in all_stacks:
				while stack:
					last_h = stack[-1]
					minsofar = last_h
					for h in stack[::-1]:
						minsofar = min(minsofar, h)
						ret += minsofar
					stack.pop()
		return ret


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		if not mat:
			return 0
		(m, n) = (len(mat), len(mat[0]))
		count = 0
		for i in range(m):
			for j in range(n):
				if mat[i][j] == 1:
					count += 1
					(up, left) = (i - 1, j - 1)
					while up >= 0 and mat[up][j] == 1:
						up -= 1
					count += i - up - 1
					while left >= 0 and mat[i][left] == 1:
						left -= 1
					count += j - left - 1
					print(i, j, up, left)
					k = i - 1
					while k > up:
						l = j - 1
						if mat[k][l] == 0:
							break
						while l > left:
							if mat[k][l] == 1:
								count += 1
								l -= 1
							else:
								left = l
								break
						k -= 1
		return count


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))
		res = 0
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				if mat[i][j] == 1:
					right_edge = n
					for res_i in range(i, m):
						if mat[res_i][j] == 0:
							break
						for res_j in range(j, right_edge):
							if mat[res_i][res_j] == 1:
								res += 1
							else:
								right_edge = min(right_edge, res_j)
								break
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		nrows = len(mat)
		ncols = len(mat[0])
		for i in range(nrows):
			for j in range(ncols):
				if mat[i][j]:
					if j > 0:
						mat[i][j] = mat[i][j - 1] + 1
		cnt = 0
		for i in range(nrows):
			for j in range(ncols):
				if mat[i][j]:
					row = i
					submatrix_width = mat[i][j]
					while row < nrows and mat[row][j]:
						submatrix_width = min(submatrix_width, mat[row][j])
						cnt += submatrix_width
						row += 1
		return cnt


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		rows = len(mat)
		columns = len(mat[0])
		count = 0
		for i in range(rows):
			for j in range(columns):
				width = columns
				for y in range(i, rows):
					if mat[y][j] == 0:
						break
					for x in range(j, width):
						if mat[y][x] == 0:
							width = x
							break
						count += 1
		return count


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(M, N) = (len(mat), len(mat[0]))

		def count_submatrices(a, b):
			(count, bound) = (0, N)
			for i in range(a, M):
				y = b
				while y < bound:
					if mat[i][y]:
						count += 1
					else:
						bound = y
					y += 1
			return count
		count = 0
		for i in range(M):
			for j in range(N):
				count += count_submatrices(i, j)
		return count


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))
		res = 0
		for j in range(n):
			for i in range(1, m):
				if mat[i][j]:
					mat[i][j] += mat[i - 1][j]
		print(mat)
		for j in range(n - 1, -1, -1):
			for i in range(m):
				if mat[i][j]:
					minval = mat[i][j]
					for k in range(j - 1, -1, -1):
						if mat[i][k] == 0:
							break
						minval = min(minval, mat[i][k])
						mat[i][j] += minval
				res += mat[i][j]
		print(mat)
		return res


from functools import lru_cache

class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		n = len(mat)
		m = len(mat[0])
		total = 0
		for i in range(n):
			for j in range(m):
				bound = m
				for k in range(i, n):
					l = j
					while l < bound:
						if mat[k][l]:
							total += 1
							l += 1
						else:
							bound = l
		return total


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		count = 0
		for i in range(len(mat)):
			for j in range(len(mat[i])):
				if mat[i][j] == 1:
					count += 1
					down = 0
					right = 0
					for x in range(i + 1, len(mat)):
						if mat[x][j] != 1:
							break
						count += 1
						down += 1
					for x in range(j + 1, len(mat[i])):
						if mat[i][x] != 1:
							break
						count += 1
						right += 1
					if down > 0 and right > 0:
						for x in range(1, down + 1):
							for y in range(1, right + 1):
								if mat[i + x][j + y] != 1:
									right = y - 1
									break
								count += 1
		return count


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		m = len(mat)
		n = len(mat[0])
		rows = []
		for row in mat:
			cur = [0]
			for x in row:
				cur.append(cur[-1] + x)
			rows.append(cur)
		res = 0
		for j2 in range(1, n + 1):
			for j1 in range(j2):
				width = j2 - j1
				pre_idx = -1
				cur = 0
				for i in range(m):
					if rows[i][j2] - rows[i][j1] != width:
						pre_idx = i
					else:
						res += i - pre_idx
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		M = len(mat)
		N = len(mat[0])
		res = 0
		for top in range(M):
			for left in range(N):
				bound = N
				for bottom in range(top, M):
					right = left
					while right < bound:
						if mat[bottom][right] == 1:
							res += 1
							right += 1
						else:
							bound = right
							break
		return res


class Solution:

	def histogramCount(self, histograms):
		stack = []
		count = 0
		out = 0
		for i in range(len(histograms)):
			while len(stack) != 0 and histograms[i] < histograms[stack[-1]]:
				j = stack.pop()
				if len(stack) == 0:
					k = -1
				else:
					k = stack[-1]
				count -= (histograms[j] - histograms[i]) * (j - k)
			count += histograms[i]
			out += count
			stack.append(i)
		return out

	def numSubmatHard(self, mat: List[List[int]]) -> int:
		prev = [0] * len(mat[0])
		out = 0
		for i in range(len(mat)):
			for j in range(len(mat[i])):
				if mat[i][j] == 0:
					prev[j] = 0
				else:
					prev[j] += mat[i][j]
			out += self.histogramCount(prev)
			print(prev, out)
		return out

	def memoization(self, grid, i, j, memo):
		if i == len(grid) or j == len(grid[0]):
			return (0, 0, 0)
		if memo[i][j] is not None:
			return memo[i][j]
		if grid[i][j] == 0:
			memo[i][j] = (0, 0, 0)
		elif i == len(grid) - 1:
			(_, col, _) = self.memoization(grid, i, j + 1, memo)
			memo[i][j] = (1, col + 1, col + 1)
		elif j == len(grid[0]) - 1:
			(row, _, _) = self.memoization(grid, i + 1, j, memo)
			memo[i][j] = (row + 1, 1, row + 1)
		else:
			(rows, _, _) = self.memoization(grid, i + 1, j, memo)
			prev = rows + 1
			out = prev
			k = j + 1
			while k < len(grid[0]) and grid[i][k] != 0:
				(row, _, _) = self.memoization(grid, i, k, memo)
				prev = min(prev, row)
				out += prev
				k += 1
			memo[i][j] = (rows + 1, k - j, out)
		return memo[i][j]

	def numSubmat(self, mat: List[List[int]]) -> int:
		memo = [[None for j in range(len(mat[0]))] for i in range(len(mat))]
		out = 0
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				(_, _, val) = self.memoization(mat, i, j, memo)
				out += val
		return out


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		rows = len(mat) - 1
		cols = len(mat[0]) - 1
		total = 0

		def find_rects(i, j):
			local = 0
			imax = rows + 1
			j_cur = j
			while j_cur <= cols:
				if mat[i][j_cur] == 0:
					break
				i_cur = i
				while i_cur < imax:
					if mat[i_cur][j_cur] == 1:
						i_cur += 1
					else:
						break
				imax = min(i_cur, imax)
				local += imax - i
				j_cur += 1
			return local
		for i in range(rows + 1):
			for j in range(cols + 1):
				if mat[i][j] == 1:
					total += find_rects(i, j)
		return total


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		if not mat or not mat[0]:
			return 0
		m = len(mat)
		n = len(mat[0])
		dp = [[0] * (n + 1) for i in range(m + 1)]
		res = 0
		for i in range(m):
			for j in range(n):
				if mat[i][j] == 1:
					dp[i + 1][j + 1] = dp[i + 1][j] + 1
					res += dp[i + 1][j + 1]
					minOnes = dp[i + 1][j + 1]
					k = i - 1
					while k >= 0 and mat[k][j] == 1:
						minOnes = min(minOnes, dp[k + 1][j + 1])
						res += minOnes
						k -= 1
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		if not mat:
			return 0
		answer = 0
		(row, col) = (len(mat), len(mat[0]))
		one_counts = [[0 for _ in range(col)] for _ in range(row)]
		for r in range(row):
			counter = 0
			for c in range(col - 1, -1, -1):
				if mat[r][c] == 1:
					counter += 1
					one_counts[r][c] = counter
				else:
					counter = 0
		for r in range(row):
			for c in range(col):
				if mat[r][c] == 1:
					min_width = float('inf')
					for k in range(r, row):
						if mat[k][c] == 1:
							min_width = min(min_width, one_counts[k][c])
							answer += min_width
							continue
						break
		return answer


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))
		res = 0
		dp = [0] * n
		for r in range(m):
			stack = []
			for c in range(n):
				cnt = 0
				if mat[r][c]:
					if r > 0:
						mat[r][c] += mat[r - 1][c]
					while stack and mat[r][stack[-1]] >= mat[r][c]:
						stack.pop()
					cnt += (c - (stack[-1] if stack else -1)) * mat[r][c]
					if stack:
						cnt += dp[stack[-1]]
				stack.append(c)
				dp[c] = cnt
				res += cnt
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		rows = len(mat)
		cols = len(mat[0])
		row_matrices = [[0] * cols for _ in range(rows)]
		for i in range(rows):
			row_matrices[i][0] = mat[i][0]
			for j in range(1, cols):
				if mat[i][j] == 1:
					row_matrices[i][j] = row_matrices[i][j - 1] + 1
				else:
					row_matrices[i][j] = 0
		result = 0
		for i in range(rows):
			for j in range(cols):
				cur_min = float('inf')
				for k in range(i, -1, -1):
					if mat[k][j] == 0:
						break
					cur_min = min(cur_min, row_matrices[k][j])
					result += cur_min
		return result


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))
		count = 0
		for left in range(n):
			row_sums = [0 for _ in range(m)]
			for right in range(left, n):
				consec_count = 0
				width = right - left + 1
				for bottom in range(m):
					row_sums[bottom] += mat[bottom][right]
					if row_sums[bottom] != width:
						consec_count = 0
					else:
						consec_count += 1
						count += consec_count
		return count


class Solution:

	def singlePointSubmat(self, mat, x, y):
		row = len(mat)
		column = len(mat[0])
		res = 0
		stoplength = column - y
		for r in range(row - x):
			if mat[x + r][y] == 1:
				res += 1
			else:
				return res
			for c in range(1, column - y):
				if c >= stoplength:
					break
				if mat[x + r][y + c] == 1:
					res += 1
				else:
					stoplength = c
		return res

	def numSubmat(self, mat: List[List[int]]) -> int:
		if len(mat) == 0 or len(mat[0]) == 0:
			return 0
		row = len(mat)
		column = len(mat[0])
		result = 0
		for r in range(row):
			for c in range(column):
				if mat[r][c] == 1:
					result += self.singlePointSubmat(mat, r, c)
		return result


import copy
from math import sqrt
from typing import List
import numpy
import sys

class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		row = len(mat)
		col = len(mat[0])
		height = [0] * col
		result = 0
		for i in range(row):
			for j in range(col):
				if mat[i][j] == 0:
					height[j] = 0
				else:
					height[j] = height[j] + 1
				k = j
				minvalue = sys.maxsize
				while k >= 0 and height[k] != 0:
					minvalue = min(minvalue, height[k])
					result += minvalue
					k -= 1
				pass
			pass
		return result


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:

		def countOneRow(arr):
			res = 0
			l = 0
			for i in range(len(arr)):
				if arr[i] == 0:
					l = 0
				else:
					l = l + 1
				res += l
			return res
		rows = len(mat)
		cols = len(mat[0])
		res = 0
		for top in range(rows):
			h = [1] * cols
			for bottom in range(top, rows):
				for c in range(cols):
					h[c] &= mat[bottom][c]
				res += countOneRow(h)
				if not any(h):
					break
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))

		def compute(h):
			res = 0
			temp = 0
			for i in range(len(h)):
				if h[i] > 0:
					temp += 1
				else:
					temp = 0
				res += temp
			return res
		ans = 0
		for i in range(m):
			h = [1] * n
			for k in range(i, m):
				for j in range(n):
					if mat[k][j] == 0:
						h[j] = 0
				ans += compute(h)
		return ans

class Solution1:

	def numSubmat(self, mat: List[List[int]]) -> int:

		def countonerow(A):
			(res, length) = (0, 0)
			for i in range(len(A)):
				length = 0 if A[i] == 0 else length + 1
				res += length
			return res

		def compute_one_row(arr):
			count = 0
			length = 0
			for a in arr:
				if a == 1:
					length += 1
				else:
					length = 0
				count += length
			return count
		(m, n) = (len(mat), len(mat[0]))
		res = 0
		for i in range(m):
			h = [1] * n
			for j in range(i, m):
				for k in range(n):
					if mat[j][k] == 0:
						h[k] = 0
				res += compute_one_row(h)
		return res

	def numSubmat1(self, mat: List[List[int]]) -> int:
		(m, n, res) = (len(mat), len(mat[0]), 0)
		histogram = [0] * (n + 1)
		for i in range(m):
			(stack, dp) = ([-1], [0] * (n + 1))
			for j in range(n):
				histogram[j] = 0 if mat[i][j] == 0 else histogram[j] + 1
				while histogram[j] < histogram[stack[-1]]:
					stack.pop()
				dp[j] = dp[stack[-1]] + histogram[j] * (j - stack[-1])
				stack.append(j)
			res += sum(dp)
		return res


class Solution:

	def numSubmat(self, a: List[List[int]]) -> int:
		m = len(a)
		n = len(a[0])

		def oneDHelper(A):
			res = 0
			l = 0
			for i in range(0, len(A)):
				if A[i] == 0:
					l = 0
				else:
					l = l + 1
				res += l
			return res
		count = 0
		for r1 in range(0, m):
			isAll1 = a[r1]
			for r2 in range(r1, m):
				for c in range(0, n):
					if a[r2][c] == 0:
						isAll1[c] = 0
				count += oneDHelper(isAll1)
		return count


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))
		for i in range(m):
			for j in range(n):
				if mat[i][j] and i > 0:
					mat[i][j] += mat[i - 1][j]
		res = 0
		for i in range(m):
			stack = []
			cnt = 0
			for j in range(n):
				while stack and mat[i][stack[-1]] > mat[i][j]:
					tmp = stack.pop()
					left = stack[-1] if stack else -1
					cnt -= (mat[i][tmp] - mat[i][j]) * (tmp - left)
				cnt += mat[i][j]
				res += cnt
				stack.append(j)
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))
		ans = 0
		for left in range(n):
			row_sum = [0 for _ in range(m)]
			for right in range(left, n):
				consec_count = 0
				w = right - left + 1
				for bottom in range(m):
					row_sum[bottom] += mat[bottom][right]
					if row_sum[bottom] != w:
						consec_count = 0
					else:
						consec_count += 1
						ans += consec_count
		return ans


class Solution:

	def countSubMat(self, rowmat: List[int]) -> int:
		length = 0
		count = 0
		for i in range(len(rowmat)):
			length = 0 if rowmat[i] == 0 else length + 1
			count += length
		return count

	def numSubmat(self, mat: List[List[int]]) -> int:
		count = 0
		for m in range(len(mat)):
			h = [1 for _ in range(len(mat[0]))]
			for down in range(m, len(mat), 1):
				for n in range(len(mat[0])):
					h[n] = h[n] and mat[down][n]
				count += self.countSubMat(h)
		return count


class Solution:

	def countOnes(self, nums):
		res = 0
		length = 0
		for i in range(len(nums)):
			length = 0 if nums[i] == 0 else length + 1
			res += length
		return res

	def numSubmat(self, mat: List[List[int]]) -> int:
		if not mat or not mat[0]:
			return 0
		(n, m) = (len(mat), len(mat[0]))
		res = 0
		for i in range(n):
			h = [1] * m
			for j in range(i, n):
				for k in range(m):
					if mat[j][k] == 0:
						h[k] = 0
				res += self.countOnes(h)
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		if not mat:
			return 0
		(m, n) = (len(mat), len(mat[0]))
		dp = [[0] * (n + 1) for _ in range(m + 1)]
		res = 0
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if mat[i - 1][j - 1]:
					dp[i][j] = dp[i][j - 1] + 1
					res += dp[i][j]
					min_ones = dp[i][j]
					for k in range(i - 1, -1, -1):
						min_ones = min(min_ones, dp[k][j])
						res += min_ones
		return res


def scan(arr, height):
	(_sum, found) = (0, 0)
	for x in arr:
		_sum = 0 if x < height else _sum + 1
		if _sum:
			found += _sum
	return found

class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(r, result) = (len(mat), 0)
		for i in range(r):
			row = mat[i]
			result += scan(row, 1)
			for k in range(i + 1, r):
				row = [x + mat[k][j] for (j, x) in enumerate(row)]
				result += scan(row, k - i + 1)
		return result


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(n, m) = (len(mat), len(mat[0]))

		def num_submat_at(a, b):
			c = 0
			bound = m
			i = a
			while i < n:
				j = b
				while j < bound:
					if mat[i][j]:
						c += 1
					else:
						bound = j
					j += 1
				i += 1
			return c
		total_c = 0
		for i in range(n):
			for j in range(m):
				total_c += num_submat_at(i, j)
		return total_c


from typing import List

def matrices_in_rect(rows: int, cols: int) -> int:
	return int(cols * (cols + 1) / 2 * (rows * (rows + 1) / 2))

class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:

		def count_rectangles(start_row: int, start_col: int) -> int:
			(rows, cols) = (len(mat), len(mat[0]) if mat else 0)
			count = 0
			max_col = cols
			for row in range(start_row, rows):
				if mat[row][start_col] != 1:
					break
				for col in range(start_col, max_col):
					if mat[row][col] != 1:
						break
					max_col = col + 1
					count += 1
			return count
		(rows, cols) = (len(mat), len(mat[0]) if mat else 0)
		count = 0
		for row in range(rows):
			for col in range(cols):
				count += count_rectangles(row, col)
		return count

	def numSubmat1(self, mat: List[List[int]]) -> int:
		(rows, cols) = (len(mat), len(mat[0]) if mat else 0)
		sizes = [[(0, 0)] * (cols + 1) for _ in range(rows + 1)]
		for row in range(rows):
			for col in range(cols):
				if mat[row][col] == 1:
					sizes[row + 1][col + 1] = (min(sizes[row][col + 1][0], sizes[row][col][0]) + 1, min(sizes[row + 1][col][1], sizes[row][col][1]) + 1)
		print(sizes)
		return 0


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:

		def oneDim(mat):
			res = 0
			length = 0
			for el in mat:
				if el == 0:
					length = 0
				else:
					length += 1
				res += length
			return res
		res = 0
		M = len(mat)
		N = len(mat[0])
		for top in range(M):
			h = [1] * N
			for bot in range(top, M):
				for i in range(N):
					h[i] *= mat[bot][i]
				res += oneDim(h)
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		m = len(mat)
		n = len(mat[0])
		ans = 0
		h = [0] * n
		for k in range(m):
			for v in range(n):
				if mat[k][v] == 1:
					h[v] += 1
				else:
					h[v] = 0
			dp = [0] * n
			dp = [0] * (n + 1)
			stack = [[-1, 0]]
			for v in range(n):
				while stack and stack[-1][0] >= h[v]:
					stack.pop()
				dp[v + 1] = dp[stack[-1][1]] + (v + 1 - stack[-1][1]) * h[v]
				stack.append([h[v], v + 1])
				ans += dp[v + 1]
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		counter = 0
		rows = len(mat)
		if rows > 0:
			columns = len(mat[0])
			for i in range(rows):
				for j in range(columns):
					max_width = 0
					max_height = 0
					if mat[i][j] == 1:
						counter += 1
						max_width += 1
						max_height += 1
						for k in range(j + 1, columns):
							if mat[i][k] == 1:
								counter += 1
								max_width += 1
							else:
								break
						for l in range(i + 1, rows):
							if mat[l][j] == 1:
								counter += 1
								max_height += 1
								m_w = 1
								for m in range(j + 1, columns):
									if mat[l][m] == 1 and m_w < max_width:
										counter += 1
										m_w += 1
									else:
										max_width = min(max_width, m_w)
										break
							else:
								break
					else:
						continue
		return counter


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		info = [[[] for i in range(len(mat[0]))] for j in range(len(mat))]
		result = 0
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				if i == 0 and j == 0:
					info[i][j].append(mat[i][j])
					result += mat[i][j]
				elif i == 0 and j != 0:
					if mat[i][j] == 1:
						info[i][j].append(info[i][j - 1][0] + 1)
						result += info[i][j][0]
					else:
						info[i][j].append(0)
				elif j == 0 and i != 0:
					if mat[i][j] == 1:
						info[i][j].append(1)
						if mat[i - 1][j] == 1:
							info[i][j] += info[i - 1][j]
						result += sum(info[i][j])
					else:
						info[i][j].append(0)
				elif mat[i][j] == 1:
					info[i][j].append(info[i][j - 1][0] + 1)
					if mat[i - 1][j] == 1:
						for index in range(len(info[i - 1][j])):
							if index + 1 < len(info[i][j - 1]):
								info[i][j].append(min(info[i][j - 1][index + 1] + 1, info[i - 1][j][index]))
							else:
								info[i][j].append(1)
					result += sum(info[i][j])
				else:
					info[i][j].append(0)
		return result


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		r = len(mat)
		c = len(mat[0])
		res = 0
		for up in range(r):
			ans = [1] * c
			for down in range(up, r):
				for j in range(c):
					ans[j] = ans[j] & mat[down][j]
				res += self.cal(ans)
		return res

	def cal(self, ans):
		res = 0
		cur = 0
		n = len(ans)
		for i in range(n):
			if ans[i] == 0:
				cur = 0
			else:
				cur += 1
				res += cur
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		n = len(mat)
		m = len(mat[0])
		counts = [[0] * m for j in range(n)]
		for i in range(n):
			for j in range(m - 1, -1, -1):
				if mat[i][j] == 1:
					counts[i][j] += 1 + (counts[i][j + 1] if j + 1 < m else 0)
		res = 0
		for i in range(n):
			for j in range(m):
				if mat[i][j] == 1:
					mins = float('inf')
					for k in range(i, n):
						mins = min(mins, counts[k][j])
						res += mins
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		a = mat
		(m, n) = (len(a), len(a[0]))

		def hist(h):
			ret = [0] * n
			s = []
			for (i, x) in enumerate(h):
				while s and h[s[-1]] >= x:
					s.pop()
				if s:
					j = s[-1]
					ret[i] = ret[j] + (i - j) * x
				else:
					ret[i] = (i + 1) * x
				s.append(i)
			return sum(ret)
		h = [0] * n
		ans = 0
		for row in a:
			for j in range(n):
				h[j] = row[j] + h[j] if row[j] else 0
			ans += hist(h)
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))
		one_counts = [[0] * n for _ in range(m)]
		for i in range(m):
			for j in range(n - 1, -1, -1):
				if mat[i][j] == 1:
					if j < n - 1:
						one_counts[i][j] += 1 + one_counts[i][j + 1]
					else:
						one_counts[i][j] = 1
		ans = 0
		for i in range(m):
			for j in range(n):
				if mat[i][j] != 1:
					continue
				min_width = sys.maxsize
				for k in range(i, m):
					min_width = min(min_width, one_counts[k][j])
					ans += min_width
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:

		def helper(arr):
			count = 0
			curr = 0
			for item in arr:
				if item != 1:
					curr = 0
				else:
					curr += 1
				count += curr
			return count
		result = 0
		for x1 in range(len(mat)):
			zeros = [1 for x in range(len(mat[0]))]
			for x2 in range(x1, len(mat)):
				for col in range(len(mat[0])):
					zeros[col] &= mat[x2][col]
				result += helper(zeros)
		return result


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		rows = len(mat) + 1
		cols = len(mat[0]) + 1
		dp = [[0 for x in range(cols)] for y in range(rows)]
		for i in range(1, rows):
			dp[i][0] = 0
		for j in range(1, cols):
			dp[0][j] = 0
		res = 0
		for i in range(1, rows):
			for j in range(1, cols):
				if mat[i - 1][j - 1] == 1:
					dp[i][j] = dp[i][j - 1] + 1
					res += dp[i][j]
					min_ones = dp[i][j]
					for k in range(i - 1, -1, -1):
						min_ones = min(dp[k][j], min_ones)
						res += min_ones
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		dp = [[0] * (len(mat[0]) + 1) for _ in range(len(mat) + 1)]
		res = 0
		for i in range(1, len(mat) + 1):
			for j in range(1, len(mat[0]) + 1):
				if mat[i - 1][j - 1] == 1:
					dp[i][j] = 1 + dp[i][j - 1]
					res += dp[i][j]
					minRec = dp[i][j]
					for k in range(i - 1, -1, -1):
						minRec = min(minRec, dp[k][j])
						res += minRec
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		count = 0
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				if mat[i][j] == 1:
					mat[i][j] = mat[i][j - 1] + 1 if j > 0 else 1
					count += mat[i][j]
					min_ones = mat[i][j]
					for k in range(i - 1, -1, -1):
						min_ones = min(min_ones, mat[k][j])
						count += min_ones
		return count


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))

		def count_sub(i, j):
			max_c = n
			count = 0
			for r in range(i, m):
				for c in range(j, max_c):
					if mat[r][c] == 1:
						count += 1
					else:
						max_c = c
						break
			return count
		ans = 0
		for i in range(m):
			for j in range(n):
				if mat[i][j]:
					ans += count_sub(i, j)
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:

		def countOneRow(A):
			(res, length) = (0, 0)
			for a in A:
				length = 0 if a == 0 else length + 1
				res += length
			return res
		(res, M, N) = (0, len(mat), len(mat[0]))
		for up in range(M):
			onesCol = [1] * N
			for down in range(up, M):
				for i in range(N):
					onesCol[i] &= mat[down][i]
				res += countOneRow(onesCol)
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(rows, cols) = (len(mat), len(mat[0]))

		def one_d_sum(h):
			ans = 0
			length = 0
			for i in range(len(h)):
				if h[i] == 1:
					length += 1
				else:
					length = 0
				ans += length
			return ans
		ans = 0
		for top_row in range(rows):
			h = [1] * cols
			for bottom_row in range(top_row, rows):
				for k in range(cols):
					h[k] = h[k] & mat[bottom_row][k]
				ans += one_d_sum(h)
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		row = len(mat)
		col = len(mat[0])
		res = 0

		def calculate1dArray(arr):
			ans = 0
			pre = 0
			for (i, a) in enumerate(arr):
				if a == 1:
					pre += 1
					ans += pre
				else:
					pre = 0
			return ans
		for a in range(row):
			arr = [1] * col
			for b in range(a, row):
				for c in range(col):
					arr[c] &= mat[b][c]
				res += calculate1dArray(arr)
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		res = 0
		(m, n) = (len(mat), len(mat[0]))
		dp = [[0] * n for i in range(m)]
		for i in range(m):
			prev = 0
			for j in range(n - 1, -1, -1):
				if mat[i][j] == 1:
					dp[i][j] = prev + 1
					prev = dp[i][j]
				else:
					prev = 0
		for i in range(m):
			for j in range(n):
				if mat[i][j] == 1:
					min_right = dp[i][j]
					for k in range(i, m):
						min_right = min(min_right, dp[k][j])
						res += min_right
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		M = len(mat)
		N = len(mat[0])
		mark = [[0 for _ in range(N)] for _ in range(M)]
		for m in range(M):
			for n in range(N):
				if n == 0:
					mark[m][n] = mat[m][n]
				else:
					mark[m][n] = mark[m][n - 1] + 1 if mat[m][n] == 1 else 0
		res = 0
		for bottom in range(M):
			for right in range(N):
				Min = mark[bottom][right]
				for upper in range(bottom + 1)[::-1]:
					Min = min(Min, mark[upper][right])
					res += Min
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))
		left = [[0 for j in range(n + 1)] for i in range(m + 1)]
		for i in range(1, len(left)):
			for j in range(1, len(left[0])):
				if mat[i - 1][j - 1] == 1:
					left[i][j] = left[i][j - 1] + 1
		res = 0
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				minlen = float('inf')
				for k in range(i, -1, -1):
					minlen = min(minlen, left[k + 1][j + 1])
					res += minlen
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))
		left_ones = [[0] * n for _ in range(m)]
		for i in range(m):
			for j in range(n):
				if mat[i][j] == 0:
					left_ones[i][j] = 0
				else:
					left_ones[i][j] = 1
					if j > 0:
						left_ones[i][j] += left_ones[i][j - 1]
		res = 0
		for j in range(n):
			total = 0
			stack = []
			for i in range(m):
				height = 1
				total += left_ones[i][j]
				while stack and stack[-1][0] > left_ones[i][j]:
					total -= stack[-1][1] * (stack[-1][0] - left_ones[i][j])
					height += stack[-1][1]
					stack.pop()
				res += total
				stack.append((left_ones[i][j], height))
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		if not mat or not mat[0]:
			return 0
		(m, n) = (len(mat), len(mat[0]))
		hts = [0] * n
		ans = 0
		for i in range(m):
			for j in range(n):
				hts[j] = hts[j] + 1 if mat[i][j] else 0
			for j in range(n):
				minh = m
				for k in range(j, n):
					minh = min(minh, hts[k])
					ans += minh
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		res = 0
		for i in range(len(mat)):
			row = [1 for _ in range(len(mat[0]))]
			for j in range(i, len(mat)):
				for k in range(len(mat[0])):
					row[k] &= mat[j][k]
				res += self.countRow(row)
		return res

	def countRow(self, row: List[int]) -> int:
		res = length = 0
		for (i, val) in enumerate(row):
			length = 0 if val == 0 else length + 1
			res += length
		return res


class Solution:

	def numSubmat(self, mat) -> int:
		(m, n) = (len(mat), len(mat[0]))
		res = 0
		for up in range(m):
			h = [1] * n
			for down in range(up, m):
				for k in range(n):
					h[k] &= mat[down][k]
				res += self.countOneRow(h)
		return res

	def countOneRow(self, arr):
		(res, length) = (0, 0)
		for i in range(len(arr)):
			length = 0 if arr[i] == 0 else length + 1
			res += length
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))
		dp = [[None for i in range(n)] for j in range(m)]
		for i in range(m):
			count = 0
			for j in range(n - 1, -1, -1):
				if mat[i][j]:
					count += 1
				else:
					count = 0
				dp[i][j] = count
		ans = 0
		for i in range(m):
			for j in range(n):
				mn = float('inf')
				for k in range(i, m):
					mn = min(mn, dp[k][j])
					ans += mn
				print()
		return ans


class Solution:

	def numSubmat(self, mat) -> int:
		(m, n) = (len(mat), len(mat[0]))
		consective = [0] * m
		res = 0
		for line in range(n):
			for row in range(m):
				if mat[row][line] == 1:
					consective[row] += 1
				else:
					consective[row] = 0
			stack = []
			for i in range(m):
				val = consective[i]
				while stack and val <= stack[-1][0]:
					stack.pop()
				stack.append((val, i))
				for k in range(len(stack)):
					if k == 0:
						(a, b) = stack[k]
						res += a * (b + 1)
					else:
						(a, b) = stack[k - 1]
						(c, d) = stack[k]
						res += c * (d - b)
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(rows, cols) = (len(mat), len(mat[0]))
		for r in range(rows):
			for c in range(1, cols):
				mat[r][c] = 1 + mat[r][c - 1] if mat[r][c] else 0
		rectangles = 0
		for r in range(rows):
			for c in range(cols):
				width = mat[r][c]
				if width:
					row = r
					while row < rows:
						width = min(width, mat[row][c])
						rectangles += width
						row += 1
		return rectangles


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:

		def rectangles_staring_at(i, j):
			res = 0
			max_col = m
			for x in range(i, n):
				for y in range(j, max_col):
					if mat[x][y] == 1:
						res += 1
					else:
						max_col = y
						break
			return res
		sums = [list(accumulate(row)) for row in mat]
		print(sums)
		(ans, n, m) = (0, len(mat), len(mat[0]))
		for i in range(n):
			for j in range(m):
				ans += rectangles_staring_at(i, j)
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(n, m) = (len(mat), len(mat[0]))
		for i in range(n):
			for j in range(m - 1):
				if mat[i][j + 1]:
					mat[i][j + 1] += mat[i][j]
		ans = 0
		for j in range(m):
			for i in range(n):
				add = mat[i][j]
				for k in range(i, n):
					add = min(add, mat[k][j])
					ans += add
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		n = len(mat)
		m = len(mat[0])
		ar = []
		for i in range(n):
			a = []
			for j in range(m):
				a.append(0)
			ar.append(a)
		for i in range(n):
			c = 0
			for j in range(m - 1, -1, -1):
				if mat[i][j] == 1:
					c += 1
				else:
					c = 0
				ar[i][j] = c
		ans = 0
		for i in range(n):
			for j in range(m):
				import sys
				x = sys.maxsize
				for k in range(i, n):
					x = min(x, ar[k][j])
					ans += x
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		R = len(mat)
		C = len(mat[0])

		def sunmat(sr, sc):
			maxc = C
			count = 0
			for x in range(sr, R):
				for y in range(sc, maxc):
					if mat[x][y] == 1:
						count += 1
					else:
						maxc = y
						break
			return count
		res = 0
		for x in range(R):
			for y in range(C):
				if mat[x][y] == 0:
					continue
				res += sunmat(x, y)
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				if j != 0 and mat[i][j] == 1:
					mat[i][j] = mat[i][j - 1] + 1
		res = 0
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				ans = mat[i][j]
				for k in range(i, len(mat)):
					ans = min(ans, mat[k][j])
					res += ans
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(R, C) = (len(mat), len(mat[0]))
		for r in range(R):
			for c in range(1, C):
				if mat[r][c]:
					mat[r][c] = mat[r][c - 1] + 1
		ans = 0
		for r in range(R):
			for c in range(C):
				if mat[r][c]:
					minWidth = mat[r][c]
					row = r
					while row < R:
						minWidth = min(minWidth, mat[row][c])
						ans += minWidth
						row += 1
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		right_ct = [[0] * len(mat[0]) for _ in range(len(mat))]
		for i in range(len(mat)):
			ct = 0
			for j in range(len(mat[0]) - 1, -1, -1):
				if mat[i][j] == 1:
					ct += 1
				else:
					ct = 0
				right_ct[i][j] = ct
		res = 0
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				right_min = float('inf')
				for k in range(i, len(mat)):
					right_min = min(right_min, right_ct[k][j])
					res += right_min
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))
		row_left_ones = [[0] * n for _ in range(m)]
		for i in range(m):
			for j in range(n):
				if mat[i][j] == 0:
					row_left_ones[i][j] = 0
				else:
					row_left_ones[i][j] = 1
					if j > 0:
						row_left_ones[i][j] += row_left_ones[i][j - 1]
		res = 0
		for i in range(m):
			for j in range(n):
				curr_row_left_ones = row_left_ones[i][j]
				for k in range(i, -1, -1):
					curr_row_left_ones = min(curr_row_left_ones, row_left_ones[k][j])
					res += curr_row_left_ones
		return res
		res = 0
		for j in range(n):
			total = 0
			stack = []
			for i in range(m):
				total += left_ones[i][j]
				width = 1
				while stack and stack[-1][0] > left_ones[i][j]:
					(last_ones, last_width) = stack.pop()
					total -= last_width * (last_ones - left_ones[i][j])
					width += last_width
				res += total
				stack.append((left_ones[i][j], width))
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		n = len(mat)
		m = len(mat[0])
		ones = [[0] * (m + 1) for _ in range(n)]
		for i in range(n):
			for j in range(m - 1, -1, -1):
				if mat[i][j] == 0:
					continue
				ones[i][j] += 1 + ones[i][j + 1]
		res = 0
		for i in range(n):
			for j in range(m):
				width = ones[i][j]
				for k in range(i, n):
					width = min(width, ones[k][j])
					res += width
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		ar = [[0] * len(mat[0]) for _ in range(len(mat))]
		for i in range(len(mat)):
			c = 0
			for j in range(len(mat[0])):
				if mat[i][j]:
					c += 1
				else:
					c = 0
				ar[i][j] = c
		for r in mat:
			print(r)
		print()
		for r in ar:
			print(r)
		print()
		ans = 0
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				x = float('inf')
				for k in range(i, len(mat)):
					x = min(x, ar[k][j])
					ans += x
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:

		def countOneRow(a):
			res = 0
			length = 0
			for el in a:
				if el == 0:
					length = 0
				else:
					length += 1
				res += length
			return res
		M = len(mat)
		N = len(mat[0])
		res = 0
		for up in range(M):
			h = [1] * N
			for down in range(up, M):
				for k in range(N):
					h[k] *= mat[down][k]
				print(h)
				res += countOneRow(h)
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		r = len(mat)
		c = len(mat[0])
		for i in range(r):
			for j in range(c - 2, -1, -1):
				if mat[i][j] != 0:
					mat[i][j] = mat[i][j + 1] + 1
		count = 0
		for i in range(r):
			for j in range(c):
				width = mat[i][j]
				for k in range(i, r):
					width = min(width, mat[k][j])
					count += width
		return count


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		ret = 0
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				maxRight = len(mat[0])
				for h in range(i, len(mat)):
					for w in range(j, maxRight):
						if mat[h][w] == 1:
							ret += 1
						else:
							maxRight = w
							break
		return ret


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		n_row = len(mat)
		if n_row == 0:
			return 0
		n_col = len(mat[0])
		if n_col == 0:
			return 0
		result = 0
		hist = [0] * (n_col + 1)
		for row in range(n_row):
			min_hist_indices = [-1]
			dp = [0] * (n_col + 1)
			for col in range(n_col):
				hist[col] = 0 if mat[row][col] == 0 else hist[col] + 1
				while hist[col] < hist[min_hist_indices[-1]]:
					min_hist_indices.pop()
				dp[col] = dp[min_hist_indices[-1]] + hist[col] * (col - min_hist_indices[-1])
				min_hist_indices.append(col)
			result += sum(dp)
		return result


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		total_sub_matrix = 0
		for row in range(len(mat)):
			for col in range(len(mat[0])):
				if mat[row][col] == 1:
					max_col = len(mat[0])
					for sub_row in range(row, len(mat)):
						for sub_col in range(col, max_col):
							if mat[sub_row][sub_col] == 0:
								max_col = sub_col
								break
							total_sub_matrix += 1
		return total_sub_matrix


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		M = len(mat)
		N = len(mat[0])
		res = 0
		for i in range(M):
			r = [1] * N
			for j in range(i, M):
				r = [r[k] & mat[j][k] for k in range(N)]
				res += self.countOneRow(r)
		return res

	def countOneRow(self, r):
		res = length = 0
		for (i, x) in enumerate(r):
			length = 0 if x == 0 else length + 1
			res += length
		return res


class Solution:

	def numSubmat(self, mat):
		(m, n) = (len(mat), len(mat[0]))
		dp = [[None for i in range(n)] for j in range(m)]
		for i in range(m):
			count = 0
			for j in range(n - 1, -1, -1):
				if mat[i][j]:
					count += 1
				else:
					count = 0
				dp[i][j] = count
		res = 0
		for i in range(m):
			for j in range(n):
				min_val = float('inf')
				for k in range(i, m):
					min_val = min(min_val, dp[k][j])
					res += min_val
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		n = len(mat)
		m = len(mat[0])
		arr = mat.copy()
		for i in range(n):
			c = 0
			for j in range(m):
				if mat[i][j]:
					c += 1
				else:
					c = 0
				arr[i][j] = c
		ans = 0
		for i in range(n):
			for j in range(m):
				x = sys.maxsize
				for k in range(i, n):
					x = min(x, arr[k][j])
					ans += x
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))
		for i in range(m):
			for j in range(n - 2, -1, -1):
				if mat[i][j] == 1:
					mat[i][j] += mat[i][j + 1]
		c = 0
		for i in range(m):
			for j in range(n):
				min_ = mat[i][j]
				for d in range(i, m):
					if not mat[i][j]:
						continue
					min_ = min(min_, mat[d][j])
					c = c + min_
		return c


from collections import defaultdict

class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(n, m) = (len(mat), len(mat[0]))
		cnt = 0

		def count(arr):
			cnt = [0] * len(arr)
			if arr[0] == 1:
				cnt[0] = 1
			for i in range(1, len(arr)):
				if arr[i] == arr[i - 1] == 1:
					cnt[i] = cnt[i - 1] + 1
				elif arr[i] == 1:
					cnt[i] = 1
				else:
					cnt[i] = 0
			return sum(cnt)
		ans = 0
		for left in range(m):
			c = [1 for i in range(n)]
			for right in range(left, m):
				for i in range(n):
					c[i] = c[i] and mat[i][right]
				ans += count(c)
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(n, m) = (len(mat), len(mat[0]))
		accs = []
		for i in range(n):
			acc = [0]
			for j in range(m):
				acc.append(acc[-1] + mat[i][j])
			accs.append(acc)
		ans = 0
		for i in range(m):
			for j in range(i, m):
				cnt = 0
				for k in range(n):
					if accs[k][j + 1] - accs[k][i] == j - i + 1:
						cnt += 1
					else:
						ans += cnt * (cnt + 1) // 2
						cnt = 0
				ans += cnt * (cnt + 1) // 2
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		mat = [[0] + row for row in mat]
		(m, n) = (len(mat), len(mat[0]))
		result = 0
		for (i, row) in enumerate(mat):
			stack = []
			count = [0] * n
			for j in range(n):
				if row[j] and i:
					row[j] += mat[i - 1][j]
				while stack and row[stack[-1]] > row[j]:
					stack.pop()
				if j and row[j]:
					count[j] = count[stack[-1]] + row[j] * (j - stack[-1])
					result += count[j]
				stack.append(j)
		return result


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		ans = 0
		N = len(mat)
		M = len(mat[0])
		row = 0
		col = 0
		for row in range(N):
			for col in range(M):
				if mat[row][col] == 0:
					continue
				else:
					i = row
					j = col
					n = N
					while j < M:
						if mat[i][j] == 0 or i == n:
							n = i
							i = row
							j += 1
						elif i + 1 == N:
							i = row
							j += 1
							ans += 1
						else:
							ans += 1
							i += 1
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		n = len(mat)
		m = len(mat[0])
		cumones = [[0] * m for x in range(n)]
		for i in range(n):
			for j in range(m - 1, -1, -1):
				if mat[i][j] == 1:
					cumones[i][j] = 1 + (cumones[i][j + 1] if j < m - 1 else 0)
		ct = 0
		for i in range(n):
			for j in range(m):
				minw = sys.maxsize
				for k in range(i, n):
					if mat[i][j] == 1:
						minw = min(minw, cumones[k][j])
						ct += minw
		return ct


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(M, N) = (len(mat), len(mat[0]))
		res = 0
		for up in range(M):
			h = [1 for i in range(N)]
			for down in range(up, M):
				for col in range(N):
					h[col] &= mat[down][col]
				res += self.oneArray(h)
		return res

	def oneArray(self, arr):
		res = length = 0
		for a in arr:
			length = 0 if a == 0 else length + 1
			res += length
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		m = len(mat)
		n = len(mat[0])
		pre = [[0] * (n + 1) for _ in range(m)]
		for row in range(m):
			for col in range(1, n + 1):
				pre[row][col] = mat[row][col - 1] + pre[row][col - 1]
		ans = 0
		for col1 in range(n):
			for col2 in range(col1 + 1, n + 1):
				local_ans = 0
				curr_stack = 0
				for row in range(m):
					if pre[row][col2] - pre[row][col1] == col2 - col1:
						curr_stack += 1
						local_ans += curr_stack
					else:
						curr_stack = 0
				ans += local_ans
		return ans


class Solution:

	def numSubmat(self, A: List[List[int]]) -> int:
		(m, n) = (len(A), len(A[0]))
		res = 0
		for i in range(m):
			r = [1] * n
			for j in range(i, m):
				for k in range(n):
					r[k] &= A[j][k]
				res += self.count(r)
		return res

	def count(self, r):
		res = head = 0
		for n in r:
			head = head + 1 if n else 0
			res += head
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		ans = 0
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				(row, col) = (0, 0)
				if mat[i][j] == 1:
					while row < len(mat) - i and mat[i + row][j] == 1:
						row += 1
					while col < len(mat[0]) - j and mat[i][j + col] == 1:
						col += 1
					(cnt, col_min) = (0, col)
					for ii in range(row):
						for jj in range(min(col_min, col)):
							if mat[i + ii][j + jj] == 1:
								cnt += 1
							else:
								col_min = jj
								break
					print((i, j, cnt))
					ans += cnt
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		ans = 0
		(N, M) = (len(mat), len(mat[0]))
		for i in range(N):
			mask = mat[i]
			for j in range(i, N):
				if j > i:
					mask = [int(i & j) for (i, j) in zip(mask, mat[j])]
				cnt = 0
				for k in mask:
					if k == 1:
						cnt += 1
					else:
						ans += cnt * (cnt + 1) // 2
						cnt = 0
				ans += cnt * (cnt + 1) // 2
		return ans


class Solution:

	def numSubmat(self, mat):
		if not mat:
			return 0
		(row, col) = (len(mat), len(mat[0]))
		for r in range(row):
			for c in range(col):
				if mat[r][c] >= 1 and r:
					mat[r][c] += mat[r - 1][c]
		answer = 0
		for row in mat:
			stack = [-1]
			num_submatrices = 0
			for (i, num) in enumerate(row):
				while stack[-1] != -1 and num <= row[stack[-1]]:
					larger_num_idx = stack.pop()
					num_submatrices -= row[larger_num_idx] * (larger_num_idx - stack[-1])
				num_submatrices += num * (i - stack[-1])
				answer += num_submatrices
				stack.append(i)
		return answer


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		res = 0
		(m, n) = (len(mat), len(mat[0]))

		def v1d(h):
			ans = 0
			length = 0
			for v in h:
				length = length + 1 if v else 0
				ans += length
			return ans
		for i in range(m):
			h = [1] * n
			for idown in range(i, m):
				for j in range(n):
					h[j] &= mat[idown][j]
				res += v1d(h)
		return res

	def numSubmat_dp_style(self, mat: List[List[int]]) -> int:
		allones = set()
		(m, n) = (len(mat), len(mat[0]))
		q = collections.deque()
		for (i, j) in itertools.product(range(m), range(n)):
			if mat[i][j]:
				q.append((i, j, 1, 1))
				allones.add((i, j, 1, 1))
		while q:
			(i, j, r, c) = q.popleft()
			if i + r < m and (i + r, j, 1, c) in allones:
				q.append((i, j, r + 1, c))
				allones.add((i, j, r + 1, c))
			if j + c < n and (i, j + c, r, 1) in allones:
				q.append((i, j, r, c + 1))
				allones.add((i, j, r, c + 1))
		return len(allones)


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		m = len(mat)
		if not m:
			return 0
		n = len(mat[0])
		dp = [[0] * n for _ in range(m)]
		for i in range(m):
			for j in range(n):
				if mat[i][j] == 1:
					if j == 0:
						dp[i][j] = 1
					else:
						dp[i][j] = dp[i][j - 1] + 1
		res = 0
		for i in range(m):
			for j in range(n):
				if mat[i][j] == 0:
					continue
				row = i
				minWidth = math.inf
				while row >= 0 and mat[i][j]:
					minWidth = min(minWidth, dp[row][j])
					res += minWidth
					row -= 1
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		n = len(mat)
		m = len(mat[0])
		ar = [[0 for j in range(m)] for i in range(n)]
		c = 0
		for i in range(n):
			c = 0
			for j in range(m - 1, -1, -1):
				if mat[i][j] == 1:
					c += 1
				else:
					c = 0
				ar[i][j] = c
		ans = 0
		for i in range(n):
			for j in range(m):
				x = float('inf')
				for k in range(i, n):
					x = min(x, ar[k][j])
					ans += x
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(M, N) = (len(mat), len(mat[0]))
		res = 0
		for top in range(M):
			h = [1 for _ in range(N)]
			for bottom in range(top, M):
				for j in range(N):
					h[j] &= mat[bottom][j]
				res += self.count1D(h)
		return res

	def count1D(self, array):
		(res, length) = (0, 0)
		for i in range(len(array)):
			if array[i] == 0:
				length = 0
			else:
				length += 1
			res += length
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		rows = len(mat)
		cols = len(mat[0])
		for r in range(rows):
			for c in range(cols):
				if mat[r][c]:
					if c > 0:
						mat[r][c] = mat[r][c - 1] + 1
		submatrices = 0
		for r in range(rows):
			for c in range(cols):
				if mat[r][c]:
					row = r
					min_value = mat[r][c]
					while row < rows and mat[r][c]:
						min_value = min(min_value, mat[row][c])
						submatrices += min_value
						row += 1
		return submatrices


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		row = len(mat)
		col = len(mat[0])
		dp = [[None] * col for _ in range(row)]
		for i in range(row):
			count = 0
			for j in range(col):
				if mat[i][j] == 1:
					count += 1
				else:
					count = 0
				dp[i][j] = count
		res = 0
		for i in range(row):
			for j in range(col):
				mn = float('inf')
				for k in range(i, row):
					mn = min(mn, dp[k][j])
					res += mn
		return res


class Solution:

	def numSubmat(self, A: List[List[int]]) -> int:
		(m, n) = (len(A), len(A[0]))
		h = [0] * n
		res = 0
		for i in range(m):
			stk = []
			psum = [0] * n
			for j in range(n):
				h[j] = h[j] + 1 if A[i][j] else 0
				while stk and h[stk[-1]] >= h[j]:
					stk.pop()
				k = stk[-1] if stk else -1
				ksum = psum[k] if stk else 0
				psum[j] = ksum + h[j] * (j - k)
				stk.append(j)
			res += sum(psum)
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		r = len(mat)
		c = len(mat[0])
		for i in range(r):
			for j in range(c - 2, -1, -1):
				if mat[i][j] == 1:
					if j < c - 1:
						mat[i][j] += mat[i][j + 1]
		res = 0
		print(mat)
		for i in range(r):
			for j in range(c):
				m = float('inf')
				for k in range(i, r):
					m = min(m, mat[k][j])
					res += m
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		m = len(mat)
		n = len(mat[0])
		ans = 0
		for i1 in range(m):
			dp = [0] * n
			for i2 in range(i1, m):
				for j in range(n):
					dp[j] += mat[i2][j]
				l = 0
				j = 0
				while j < n:
					if dp[j] == i2 - i1 + 1:
						l += 1
					else:
						ans += l * (l + 1) // 2
						l = 0
					j += 1
				if l > 0:
					ans += l * (l + 1) // 2
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		m = len(mat)
		n = len(mat[0])

		def count_submatrices(r, c):
			count = 0
			bound = n
			for i in range(r, m):
				for j in range(c, bound):
					if j >= bound:
						continue
					elif mat[i][j] == 1:
						count += 1
					else:
						bound = j
			return count
		total_count = 0
		for (r, row) in enumerate(mat):
			for (c, cell) in enumerate(row):
				total_count += count_submatrices(r, c)
		return total_count


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:

		def counts(nums):
			endhere = [0] * len(nums)
			st = []
			for (i, num) in enumerate(nums):
				while st and nums[st[-1]] >= num:
					st.pop()
				if not st:
					endhere[i] = num * (i + 1)
				else:
					prev_idx = st[-1]
					endhere[i] = endhere[prev_idx]
					endhere[i] += num * (i - prev_idx)
				st.append(i)
			return sum(endhere)
		rows = mat[0][:]
		ans = counts(rows[:])
		for i in range(1, len(mat)):
			for j in range(len(mat[0])):
				if mat[i][j] == 1:
					rows[j] += 1
				else:
					rows[j] = 0
			ans += counts(rows[:])
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))
		for i in range(m):
			for j in range(n):
				if mat[i][j] and i > 0:
					mat[i][j] += mat[i - 1][j]
		ans = 0
		for i in range(m):
			stack = []
			cnt = 0
			for j in range(n):
				while stack and mat[i][stack[-1]] > mat[i][j]:
					jj = stack.pop()
					kk = stack[-1] if stack else -1
					cnt -= (mat[i][jj] - mat[i][j]) * (jj - kk)
				cnt += mat[i][j]
				ans += cnt
				stack.append(j)
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		m = len(mat)
		n = len(mat[0])
		tot = 0
		for i in range(m):
			prev = []
			for j in range(n):
				if not mat[i][j]:
					prev = []
					continue
				if i > 0:
					mat[i][j] += mat[i - 1][j]
				h = mat[i][j]
				tot += h
				for p in range(len(prev) - 1, -1, -1):
					if prev[p] > h:
						prev[p] = h
					tot += prev[p]
				prev.append(h)
		return tot


class Solution:

	def helper(self, heights, n):
		stack = []
		res = [0] * n
		for i in range(n):
			while stack and heights[stack[-1]] >= heights[i]:
				stack.pop()
			if stack:
				prev = stack[-1]
				res[i] = res[prev] + heights[i] * (i - prev)
			else:
				res[i] = heights[i] * (i + 1)
			stack.append(i)
		return sum(res)

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))
		heights = [[0] * n for _ in range(m)]
		res = 0
		for j in range(n):
			if mat[0][j] == 1:
				heights[0][j] = 1
		for i in range(1, m):
			for j in range(n):
				if mat[i][j] == 1:
					heights[i][j] = heights[i - 1][j] + 1
		for i in range(m):
			res += self.helper(heights[i], n)
		return res


class Solution:

	def helper(self, arr):
		tracker = [0] * len(arr)
		stack = []
		for i in range(len(arr)):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			if stack:
				tracker[i] = tracker[stack[-1]]
				tracker[i] += arr[i] * (i - stack[-1])
			else:
				tracker[i] = arr[i] * (i + 1)
			stack.append(i)
		return sum(tracker)

	def numSubmat(self, mat: List[List[int]]) -> int:
		m = len(mat)
		n = len(mat[0])
		column_track = [0] * n
		res = 0
		for i in range(m):
			for j in range(n):
				column_track[j] = 0 if mat[i][j] == 0 else column_track[j] + 1
			res += self.helper(column_track)
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n, res) = (len(mat), len(mat[0]), 0)
		histogram = [0] * (n + 1)
		for i in range(m):
			(stack, dp) = ([-1], [0] * (n + 1))
			for j in range(n):
				if mat[i][j] == 0:
					histogram[j] = 0
				else:
					histogram[j] += 1
				while histogram[j] < histogram[stack[-1]]:
					stack.pop()
				dp[j] = dp[stack[-1]] + histogram[j] * (j - stack[-1])
				stack.append(j)
			res += sum(dp)
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:

		def pom(tab):
			stack = []
			sums = [0] * len(tab)
			for i in range(len(tab)):
				while len(stack) > 0 and tab[stack[-1]] > tab[i]:
					stack.pop()
				if len(stack) == 0:
					sums[i] = (i + 1) * tab[i]
				else:
					sums[i] = sums[stack[-1]] + tab[i] * (i - stack[-1])
				stack.append(i)
			return sum(sums)
		n_rows = len(mat)
		n_cols = len(mat[0])
		h = [0] * n_cols
		res = 0
		for row in mat:
			for i in range(len(row)):
				if row[i] == 1:
					h[i] += 1
				else:
					h[i] = 0
			res += pom(h)
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(M, N) = (len(mat), len(mat[0]))
		for i in range(1, M):
			for j in range(N):
				if mat[i][j]:
					mat[i][j] += mat[i - 1][j]
		result = 0
		for row in mat:
			count = [0] * N
			stk = []
			for (i, e) in enumerate(row):
				while stk and row[stk[-1]] >= e:
					stk.pop()
				if stk:
					count[i] = count[stk[-1]] + e * (i - stk[-1])
				else:
					count[i] = e * (i + 1)
				stk.append(i)
			result += sum(count)
		return result


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		if not mat:
			return 0
		m = len(mat)
		n = len(mat[0])
		for y in range(m):
			for x in range(n):
				if mat[y][x] and y > 0:
					mat[y][x] += mat[y - 1][x]
		ans = 0
		for y in range(m):
			stack = []
			cnt = 0
			for x in range(n):
				while stack and mat[y][stack[-1]] > mat[y][x]:
					prev_hist_end = stack.pop()
					prev_hist_start = stack[-1] if stack else -1
					cnt -= (prev_hist_end - prev_hist_start) * (mat[y][prev_hist_end] - mat[y][x])
				cnt += mat[y][x]
				ans += cnt
				stack.append(x)
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		if not mat:
			return 0
		(m, n) = (len(mat), len(mat[0]))
		ans = 0
		colCount = [0] * n
		for i in range(m):
			rowCount = 0
			colCount1 = [0] * n
			for j in range(n):
				if mat[i][j]:
					rowCount += 1
					colCount1[j] = colCount[j] + 1
					minColCount = math.inf
					for k in range(j, j - rowCount, -1):
						minColCount = min(minColCount, colCount1[k])
						ans += minColCount
				else:
					colCount1[j] = 0
					rowCount = 0
			colCount = colCount1
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))
		for r in range(m):
			for c in range(n):
				if mat[r][c] and r > 0:
					mat[r][c] += mat[r - 1][c]
		res = 0
		for r in range(m):
			count = 0
			stack = []
			for c in range(n):
				while stack and mat[r][stack[-1]] > mat[r][c]:
					j = stack.pop()
					w = stack[-1] if stack else -1
					count -= (mat[r][j] - mat[r][c]) * (j - w)
				count += mat[r][c]
				res += count
				stack.append(c)
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		ans = 0
		M = len(mat)
		if M == 0:
			return 0
		N = len(mat[0])
		count = [0 for _ in range(N)]
		ans = 0
		for i in range(M):
			rowcount = 0
			for j in range(N):
				if mat[i][j] == 1:
					count[j] += 1
					rowcount += 1
					minV = 1 << 30
					for k in range(j, j - rowcount, -1):
						minV = min(minV, count[k])
						ans += minV
				else:
					rowcount = 0
					count[j] = 0
		return ans


class Solution:

	def numSubmat1(self, mat: List[List[int]]) -> int:
		(m, n, res) = (len(mat), len(mat[0]), 0)
		histogram = [0] * n
		for i in range(m):
			(stack, dp) = ([], [0] * n)
			for j in range(n):
				histogram[j] = 0 if mat[i][j] == 0 else histogram[j] + 1
				while stack and histogram[j] < histogram[stack[-1]]:
					stack.pop()
				if stack:
					dp[j] = dp[stack[-1]] + histogram[j] * (j - stack[-1])
				else:
					dp[j] = histogram[j] * (j + 1)
				stack.append(j)
			res += sum(dp)
			print(res)
		return res

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))
		count = 0
		hist = [0] * n
		for i in range(m):
			dp = [0] * n
			for j in range(n):
				if mat[i][j] == 1:
					hist[j] += 1
				else:
					hist[j] = 0
			stack = []
			for (j, h) in enumerate(hist):
				while stack and hist[stack[-1]] >= h:
					stack.pop()
				if stack:
					dp[j] = dp[stack[-1]] + hist[j] * (j - stack[-1])
				else:
					dp[j] = hist[j] * (j + 1)
				stack.append(j)
			count += sum(dp)
			print(count)
		return count


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		lim1 = len(mat)
		lim2 = len(mat[0])
		hz = [[0 for j in range(0, lim2)] for i in range(0, lim1)]
		t = 0
		for i in range(lim1 - 1, -1, -1):
			for j in range(lim2 - 1, -1, -1):
				if mat[i][j] != 0:
					if j < lim2 - 1:
						hz[i][j] += hz[i][j + 1] + 1
					else:
						hz[i][j] = 1
		vt = [[0 for j in range(0, lim2)] for i in range(0, lim1)]
		for i in range(0, lim1):
			for j in range(0, lim2):
				if hz[i][j] != 0:
					mn = 99999999999
					for k in range(i, lim1):
						if hz[k][j] == 0:
							break
						elif hz[k][j] < mn:
							mn = hz[k][j]
						t += mn
		return t


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))
		dp = [[0] * n for _ in range(m)]
		res = 0
		for i in range(m):
			dp[i][0] = 1 if mat[i][0] == 1 else 0
			res += dp[i][0]
			mini = dp[i][0]
			for k in range(i - 1, -1, -1):
				mini = min(mini, dp[k][0])
				res += mini
				if mini == 0:
					break
			for j in range(1, n):
				if mat[i][j] == 1:
					dp[i][j] = dp[i][j - 1] + 1
					res += dp[i][j]
					mini = dp[i][j]
					for k in range(i - 1, -1, -1):
						mini = min(mini, dp[k][j])
						res += mini
						if mini == 0:
							break
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		if not mat:
			return 0
		(rows, cols) = (len(mat), len(mat[0]))
		height = [0] * cols
		output = 0
		for r in range(rows):
			for c in range(cols):
				if mat[r][c] == 0:
					height[c] = 0
				else:
					height[c] += 1
					v = height[c]
					for i in range(c, -1, -1):
						if height[i] == 0:
							break
						v = min(v, height[i])
						output += v
		return output
		1 + 1 + 2 + 1 + 1 + 3 + 2 + 2


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(h, w) = (len(mat), len(mat[0]))
		dp_acc_of_1 = [[0 for _ in range(w)] for _ in range(h)]
		for y in range(h):
			for x in range(w):
				if x == 0:
					dp_acc_of_1[y][x] = mat[y][x]
				elif mat[y][x] == 1:
					dp_acc_of_1[y][x] = dp_acc_of_1[y][x - 1] + 1
		counter_of_rectangle = 0
		for y in range(h):
			for x in range(w):
				minimum_width = dp_acc_of_1[y][x]
				for h_idx in range(y, -1, -1):
					minimum_width = min(minimum_width, dp_acc_of_1[h_idx][x])
					counter_of_rectangle += minimum_width
					if minimum_width == 0:
						break
		return counter_of_rectangle


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(acc, his) = (0, [0] * len(mat[0]))
		for (i, row) in enumerate(mat):
			for (j, v) in enumerate(row):
				his[j] = his[j] + 1 if v else 0
				cap = float('inf')
				for height in his[:j + 1][::-1]:
					cap = min(cap, height)
					if not cap:
						break
					acc += cap
		return acc


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		if not mat:
			return 0
		(m, n) = (len(mat), len(mat[0]))
		ret = 0
		height = [0] * n
		for i in range(m):
			for j in range(n):
				height[j] = 0 if not mat[i][j] else height[j] + 1
				if mat[i][j]:
					h = height[j]
					for k in range(j, -1, -1):
						if mat[i][k]:
							h = min(h, height[k])
							ret += h
						else:
							break
		return ret


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		res = 0
		m = mat
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				if j > 0 and mat[i][j] == 1:
					m[i][j] = m[i][j - 1] + 1
		for j in range(len(mat[0])):
			for i in range(len(mat)):
				mn = m[i][j]
				for k in range(i, -1, -1):
					mn = min(mn, m[k][j])
					if mn == 0:
						break
					res += mn
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		for i in range(1, len(mat)):
			for j in range(len(mat[0])):
				if mat[i][j]:
					mat[i][j] += mat[i - 1][j]
		ans = 0
		for i in range(len(mat)):
			stack = []
			cnt = 0
			for j in range(len(mat[0])):
				while stack and mat[i][stack[-1]] > mat[i][j]:
					last = stack.pop()
					prev = stack[-1] if stack else -1
					cnt -= (mat[i][last] - mat[i][j]) * (last - prev)
				cnt += mat[i][j]
				ans += cnt
				stack.append(j)
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))
		up = [[0] * n for _ in range(m)]
		count = 0
		for i in range(m):
			for j in range(n):
				if not mat[i][j]:
					continue
				if i == 0:
					up[i][j] = 1
				else:
					up[i][j] = up[i - 1][j] + 1
				k = j
				min_height = up[i][j]
				while k >= 0 and mat[i][k]:
					min_height = min(min_height, up[i][k])
					count += min_height
					k -= 1
		return count


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		H = mat
		for i in range(1, len(mat)):
			for j in range(len(mat[0])):
				if H[i][j] == 0:
					continue
				H[i][j] = H[i - 1][j] + 1
		total = 0
		for i in range(len(H)):
			for j in range(len(H[0])):
				if H[i][j] == 0:
					continue
				h = H[i][j]
				total += h
				for k in range(j + 1, len(H[0])):
					if H[i][k] == 0:
						break
					h = min(H[i][k], h)
					total += h
		return total


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		m = len(mat)
		n = len(mat[0])
		heights = [0] * n
		count = 0
		for i in range(m):
			for j in range(n):
				if mat[i][j] == 0:
					heights[j] = 0
				else:
					heights[j] += 1
			for j in range(n):
				k = j
				smallest_height = heights[k]
				while k > -1 and heights[k] > 0:
					smallest_height = min(smallest_height, heights[k])
					count += smallest_height
					k -= 1
		return count


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		nums = [[0] * len(mat[0]) for _ in range(len(mat))]
		for row in range(len(mat)):
			for col in range(len(mat[0])):
				if col == 0:
					nums[row][col] = mat[row][col]
				elif mat[row][col] == 0:
					nums[row][col] = 0
				else:
					nums[row][col] = nums[row][col - 1] + 1
		res = 0
		for row in range(len(mat)):
			for col in range(len(mat[0])):
				Min = nums[row][col]
				k = row
				while k >= 0:
					if nums[k][col] == 0:
						break
					Min = min(nums[k][col], Min)
					res += Min
					k -= 1
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))
		for i in range(m):
			for j in range(n):
				if mat[i][j]:
					if j > 0:
						mat[i][j] = mat[i][j - 1] + 1
		total = 0
		for i in range(m):
			for j in range(n):
				if mat[i][j]:
					row = i
					width = mat[i][j]
					while row < m and mat[row][j]:
						width = min(width, mat[row][j])
						total += width
						row += 1
		return total


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		if len(mat) == 0:
			return 0
		hist = [0] * len(mat[0])
		res = 0
		for row in mat:
			stack = []
			count = 0
			for i in range(len(row)):
				if row[i]:
					hist[i] += row[i]
				else:
					hist[i] = 0
				while stack and hist[stack[-1]] > hist[i]:
					jj = stack.pop()
					kk = stack[-1] if stack else -1
					count -= (hist[jj] - hist[i]) * (jj - kk)
				count += hist[i]
				res += count
				stack.append(i)
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		n = len(mat)
		m = len(mat[0])
		count = 0
		dp = [[0] * m for _ in range(n)]
		for i in range(n):
			c = 0
			for j in range(m - 1, -1, -1):
				if mat[i][j]:
					c += 1
				else:
					c = 0
				dp[i][j] = c
		for j in range(m):
			for i in range(n):
				if dp[i][j]:
					min_v = dp[i][j]
					count += dp[i][j]
					for k in range(i + 1, n):
						min_v = min(min_v, dp[k][j])
						if not min_v:
							break
						count += (k - i + 1) * min_v - (k - i) * min_v
		return count


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		for j in range(len(mat[0])):
			for i in range(1, len(mat)):
				if mat[i][j] != 0:
					if mat[i - 1][j] != 0:
						mat[i][j] = mat[i - 1][j] + 1
		cnt = 0
		for i in range(0, len(mat)):
			for j in range(len(mat[0])):
				min_height = len(mat)
				for k in range(j, -1, -1):
					if mat[i][k] == 0:
						break
					min_height = min(min_height, mat[i][k])
					cnt += min_height
		return cnt


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		res = 0
		for i in range(len(mat)):
			for j in range(1, len(mat[0])):
				if mat[i][j]:
					if j > 0:
						mat[i][j] = mat[i][j - 1] + 1
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				if mat[i][j]:
					r = i
					wid = mat[i][j]
					while r < len(mat) and mat[r][j]:
						wid = min(mat[r][j], wid)
						res += wid
						r += 1
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:

		def func(i, j):
			res = 0
			height = float('inf')
			for jj in range(j, -1, -1):
				height = min(height, cnt[i][jj][1])
				if not height:
					break
				res += height
			return res
		(n, m) = (len(mat), len(mat[0]))
		cnt = [[0] * m for _ in range(n)]
		tot = 0
		for i in range(n):
			for j in range(m):
				if not mat[i][j]:
					cnt[i][j] = (0, 0)
				else:
					lft = cnt[i][j - 1][0] + 1 if j > 0 else 1
					top = cnt[i - 1][j][1] + 1 if i > 0 else 1
					cnt[i][j] = (lft, top)
					tot += func(i, j)
		return tot


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:

		def helper(h):
			res = 0
			st = []
			sum_ = [0] * len(h)
			for i in range(len(h)):
				while len(st) > 0 and h[st[-1]] >= h[i]:
					st.pop()
				if len(st) > 0:
					left_bound = st[-1]
					sum_[i] += sum_[left_bound]
					sum_[i] += h[i] * (i - left_bound)
				else:
					sum_[i] = h[i] * (i + 1)
				st.append(i)
			return sum(sum_)
		res = 0
		h = [0] * len(mat[0])
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				if mat[i][j] == 1:
					h[j] += 1
				else:
					h[j] = 0
			res += helper(h)
		return res


class Solution:

	def numSubmat(self, g: List[List[int]]) -> int:
		(rows, cols, res) = (len(g), len(g[0]), 0)
		for r in range(rows):
			width = 0
			for c in range(cols):
				if g[r][c]:
					width += 1
					g[r][c] = width
				else:
					width = 0
				res += width
				(row, prev_width) = (r, width)
				while row > 0 and g[row - 1][c]:
					prev_width = min(prev_width, g[row - 1][c])
					res = res + prev_width
					row -= 1
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		row = len(mat)
		col = len(mat[0])
		res = 0
		dp = [[0 for _ in range(col)] for _ in range(row)]
		for i in range(row):
			for j in range(col - 1, -1, -1):
				if mat[i][j] == 1:
					dp[i][j] = mat[i][j]
					if j < col - 1:
						dp[i][j] += dp[i][j + 1]
		print(dp)
		for i in range(row):
			for j in range(col):
				if mat[i][j] == 1:
					curr_row = i
					width = dp[curr_row][j]
					while curr_row < row and dp[curr_row][j] >= 1:
						width = min(dp[curr_row][j], width)
						res += width
						curr_row += 1
		return res


class Solution:

	def numSubmat(self, mat) -> int:
		(m, n) = (len(mat), len(mat[0]))
		self.count = 0
		for i in range(m):
			for j in range(n):
				if mat[i][j]:
					if j > 0:
						mat[i][j] += mat[i][j - 1]
		for i in range(m):
			for j in range(n):
				if mat[i][j]:
					row = i
					submatrix_width = mat[i][j]
					while row < m and mat[row][j]:
						submatrix_width = min(submatrix_width, mat[row][j])
						self.count += submatrix_width
						row += 1
		return self.count


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		if not mat:
			return 0
		for row in range(len(mat)):
			for col in range(len(mat[0])):
				count = 0
				if mat[row][col] == 1:
					for index in range(col, len(mat[0])):
						if mat[row][index]:
							count += 1
						else:
							break
				mat[row][col] = count
		ans = 0
		for row in range(len(mat)):
			for col in range(len(mat[0])):
				count = 0
				if mat[row][col]:
					min_width = mat[row][col]
					for index in range(row, len(mat)):
						if not mat[index][col]:
							break
						min_width = min(min_width, mat[index][col])
						count += min_width
				ans += count
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		rows = len(mat)
		cols = len(mat[0])
		dp = [[0 for _ in range(cols)] for _ in range(rows)]
		for r in range(rows):
			for c in range(cols):
				if c == 0:
					dp[r][c] = mat[r][c]
				elif mat[r][c] == 1:
					dp[r][c] = dp[r][c - 1] + 1
		count = 0
		for r in range(rows):
			for c in range(cols):
				min_width = dp[r][c]
				for h_idx in range(r, -1, -1):
					min_width = min(min_width, dp[h_idx][c])
					count += min_width
					if min_width == 0:
						break
		return count


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		dp = [[0 for _ in range(len(mat[0]))] for _ in range(len(mat))]
		for i in range(len(mat)):
			for j in range(len(mat[0]) - 1, -1, -1):
				if mat[i][j] == 1:
					dp[i][j] = 1 + (dp[i][j + 1] if j < len(mat[0]) - 1 else 0)
		ans = 0
		for j in range(len(mat[0])):
			for i in range(len(mat)):
				t = float('inf')
				for k in range(i, len(mat)):
					t = min(t, dp[k][j])
					if t == 0:
						break
					else:
						ans += t
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		m = len(mat)
		if m == 0:
			return 0
		n = len(mat[0])
		if n == 0:
			return 0
		temp = [0, 0]
		count = [[[0] * 2 for l in range(n)] for _ in range(m)]
		res = 0
		for i in range(m):
			for j in range(n):
				if i == 0 and j == 0:
					res += mat[i][j]
					count[i][j][0] = mat[i][j]
					count[i][j][1] = mat[i][j]
					continue
				elif i == 0 and mat[i][j]:
					count[i][j][1] += count[i][j - 1][1] + 1
					res += count[i][j][1]
					count[i][j][0] = mat[i][j]
				elif j == 0 and mat[i][j]:
					count[i][j][0] += count[i - 1][j][0] + 1
					res += count[i][j][0]
					count[i][j][1] = mat[i][j]
				elif mat[i][j]:
					res += 1
					count[i][j][1] += count[i][j - 1][1] + 1
					count[i][j][0] += count[i - 1][j][0] + 1
					if count[i][j - 1][1]:
						res += count[i][j - 1][1]
					if count[i - 1][j][0]:
						res += count[i - 1][j][0]
					findmin = count[i][j][0]
					for k in range(1, count[i][j][1]):
						findmin = min(findmin, count[i][j - k][0])
						res += findmin - 1
		return res


from functools import lru_cache
from itertools import product

class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(R, C) = (len(mat), len(mat[0]))

		@lru_cache(None)
		def leftsum(i, j):
			if j < 0 or mat[i][j] == 0:
				return 0
			return 1 + leftsum(i, j - 1)
		ret = 0
		for (bottom, j) in product(list(range(R)), list(range(C))):
			width = j + 1
			for top in range(bottom, -1, -1):
				width = min(leftsum(top, j), width)
				if width == 0:
					break
				ret += width
		return ret


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		count = 0
		r = len(mat)
		c = len(mat[0])
		for i in range(r):
			for j in range(c - 2, -1, -1):
				if mat[i][j] == 1:
					mat[i][j] += mat[i][j + 1]
		for i in range(r):
			for j in range(c):
				minm = mat[i][j]
				d = i
				while d < r and mat[d][j] != 0:
					minm = min(minm, mat[d][j])
					count += minm
					d += 1
		return count


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		m = len(mat)
		if m == 0:
			return 0
		n = len(mat[0])
		if n == 0:
			return 0
		dp = [[0] * n for _ in range(m)]
		for i in range(m):
			for j in range(n):
				if j == 0:
					dp[i][j] = mat[i][j]
				elif mat[i][j] == 1:
					dp[i][j] = dp[i][j - 1] + 1
		result = 0
		for i in range(m):
			for j in range(n):
				min_width = dp[i][j]
				for row_idx in range(i, -1, -1):
					min_width = min(min_width, dp[row_idx][j])
					result += min_width
					if min_width == 0:
						break
		return result


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		if not mat:
			return 0
		rows = len(mat)
		cols = len(mat[0])
		n = 0
		for top in range(rows):
			for left in range(cols):
				bottom = rows
				for right in range(left, cols):
					scan = top
					while scan < bottom and mat[scan][right]:
						scan += 1
					bottom = scan
					n += bottom - top
					if bottom == top:
						break
		return n


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		n = len(mat)
		m = len(mat[0])
		width = [[0 for _ in range(m)] for _ in range(n)]
		for i in range(n):
			width[i][0] = mat[i][0]
		for i in range(n):
			for j in range(1, m):
				if mat[i][j] != 0:
					width[i][j] = width[i][j - 1] + 1
		ans = 0
		for i in range(n):
			for j in range(m):
				if mat[i][j] != 0:
					min_width = width[i][j]
					for new_i in range(i, -1, -1):
						if mat[new_i][j] == 0:
							break
						min_width = min(min_width, width[new_i][j])
						ans += min_width
		return ans


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(m, n) = (len(mat), len(mat[0]))
		for i in range(1, m):
			for j in range(n):
				if mat[i][j]:
					mat[i][j] += mat[i - 1][j]
		result = 0
		for i in range(m):
			for k in range(i, m):
				height = k - i + 1
				width = 0
				for j in range(n):
					if mat[k][j] >= height:
						width += 1
						result += width
					else:
						width = 0
		return result


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				if not mat[i][j]:
					continue
				mat[i][j] += mat[i - 1][j] if i - 1 >= 0 else 0
		ret = 0
		for i in range(len(mat)):
			row = mat[i]
			stack = []
			tot = 0
			for j in range(len(row)):
				ths = 1
				while stack and stack[-1][0] >= row[j]:
					popped = stack.pop()
					tot -= popped[0] * popped[1]
					ths += popped[1]
				stack.append([row[j], ths])
				tot += ths * row[j]
				ret += tot
		return ret


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		dph = [[0 for j in range(len(mat[0]) + 1)] for i in range(len(mat) + 1)]
		dpv = [[0 for j in range(len(mat[0]) + 1)] for i in range(len(mat) + 1)]
		dps = [[[] for j in range(len(mat[0]) + 1)] for i in range(len(mat) + 1)]
		counts = 0
		for i in range(1, len(mat) + 1):
			for j in range(1, len(mat[0]) + 1):
				if mat[i - 1][j - 1] == 1:
					dpv[i][j] = dpv[i - 1][j] + 1
					dph[i][j] = dph[i][j - 1] + 1
					if dpv[i][j] - 1 > dpv[i - 1][j - 1]:
						tmp = collections.deque([dph[i][j]])
						for k in range(dpv[i][j] - 1):
							if k < dpv[i - 1][j - 1]:
								tmp.append(min(dps[i - 1][j - 1][k] + 1, dph[i][j]))
							else:
								tmp.append(1)
					else:
						tmp = collections.deque([dph[i][j]])
						for k in range(dpv[i][j] - 1):
							tmp.append(min(dps[i - 1][j - 1][k] + 1, dph[i][j]))
					dps[i][j] = tmp
					counts += sum(tmp)
		print(dps)
		return counts


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		m = len(mat)
		n = len(mat[0])
		dp = [[mat[i][j] for j in range(n)] for i in range(m)]
		for i in range(m):
			for j in range(n - 2, -1, -1):
				if mat[i][j] == 1:
					dp[i][j] = dp[i][j + 1] + 1
		res = 0
		for i in range(m):
			for j in range(n):
				k = i
				mn = dp[i][j]
				while k < m and dp[k][j] != 0:
					mn = min(mn, dp[k][j])
					res += mn
					k += 1
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		result = 0
		n = len(mat)
		m = len(mat[0])
		consecutive_ones = [[0] * m for _ in range(n)]
		overall_ones = []
		for i in range(n):
			c = 0
			for j in range(m - 1, -1, -1):
				if mat[i][j] == 1:
					c += 1
					overall_ones.append((i, j))
				else:
					c = 0
				consecutive_ones[i][j] = c
		while len(overall_ones) != 0:
			leftmost_point = overall_ones.pop()
			i = leftmost_point[0]
			j = leftmost_point[1]
			prev_row_width = float('inf')
			for row in range(i, n):
				curr_width = consecutive_ones[row][j]
				if curr_width == 0:
					break
				result += min(prev_row_width, curr_width)
				prev_row_width = min(prev_row_width, curr_width)
		return result


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		m = len(mat)
		n = len(mat[0])
		for i in range(m):
			for j in reversed(range(n - 1)):
				if mat[i][j] == 1:
					mat[i][j] = mat[i][j + 1] + 1

		def countSubmat(i, j):
			top = i
			left = j
			bound = n
			counter = 0
			while i < m and mat[i][j] > 0:
				counter += min(bound, mat[i][j])
				bound = min(bound, mat[i][j])
				i += 1
			return counter
		total = 0
		for i in range(m):
			for j in range(n):
				if mat[i][j] > 0:
					total += countSubmat(i, j)
		return total


class Solution:

	def get_matrix_cnt(self, cur_row_height):
		res = 0
		for (i, polm) in enumerate(cur_row_height):
			if polm > 0:
				for cur_height in range(1, polm + 1):
					res += 1
					cur_index = i + 1
					while cur_index < len(cur_row_height) and cur_row_height[cur_index] >= cur_height:
						res += 1
						cur_index += 1
		return res

	def numSubmat(self, mat: List[List[int]]) -> int:
		m = len(mat)
		n = len(mat[0])
		cur_row_height = [0] * n
		total = 0
		for row in range(m):
			for col in range(n):
				if mat[row][col] == 0:
					cur_row_height[col] = 0
				else:
					cur_row_height[col] += 1
			cur_cnt = self.get_matrix_cnt(cur_row_height)
			total += cur_cnt
		return total


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		(res, lr, lc) = (0, len(mat), len(mat[0]) if mat else 0)
		for i in range(lr):
			for j in range(lc):
				if mat[i][j]:
					(cur, x, limit) = (0, i, lc)
					while x < lr:
						y = j
						if not mat[x][y]:
							break
						while y < limit:
							if not mat[x][y]:
								limit = y
								break
							(cur, y) = (cur + 1, y + 1)
						x += 1
					res += cur
		return res


class Solution:

	def numSubmat(self, mat: List[List[int]]) -> int:
		m = len(mat)
		if m == 0:
			return 0
		n = len(mat[0])
		if n == 0:
			return 0
		a = [None for _ in range(m)]
		for i in range(m):
			a[i] = []
			for j in range(n):
				a[i].append([0, 0])
		for i in range(m):
			for j in range(n - 1, -1, -1):
				if i == n - 1:
					a[i][j][0] = 1 if mat[i][j] == 1 else 0
				else:
					a[i][j][0] = 1 + a[i - 1][j][0] if mat[i][j] == 1 else 0
		for j in range(n):
			for i in range(m):
				if i == 0:
					a[i][j][1] = 1 if mat[i][j] == 1 else 0
				else:
					a[i][j][1] = 1 + a[i - 1][j][1] if mat[i][j] == 1 else 0
		ans = 0
		for i in range(m):
			j = 0
			while j < n:
				if mat[i][j] == 0:
					j += 1
				else:
					minH = a[i][j][1]
					k = j
					while k < n and mat[i][k] == 1:
						minH = min(minH, a[i][k][1])
						ans += minH
						k += 1
					j += 1
		return ans