Count Submatrices with All Ones

You get a grid mat of 0s and 1s, with m rows and n columns. Return how many rectangles in the grid hold only 1s.

A rectangle can be a single cell, a strip of cells, or a bigger block. Two rectangles that cover different cells count as two.

Example 1:

Input: mat = [[1,1,0],[1,1,1]]
Output: 12
Explanation: Counted by size (rows x columns):
5 of size 1 x 1, one for each 1,
3 of size 1 x 2,
1 of size 1 x 3, the whole bottom row,
2 of size 2 x 1,
1 of size 2 x 2, the left two columns.
In total, 5 + 3 + 1 + 2 + 1 = 12.

Example 2:

Input: mat = [[1,1,1,0,1]]
Output: 7
Explanation: The 0 cuts the row in two.
Counted by size:
4 single cells,
2 pairs side by side, both before the 0,
1 strip of three, also before the 0.
In total, 4 + 2 + 1 = 7.

Example 3:

Input: mat = [[0,0],[0,0]]
Output: 0
Explanation: No cell holds a 1, so there is nothing to count.

Constraints:

• m and n are each between 1 and 150.
• Every cell of mat holds 0 or 1.