Rectangles That Sum to Target

grid is a rectangle of integers stored as a list of rows. Write count_submatrices(grid, target) that counts the rectangular blocks of the grid whose values add up to target.

A block is any choice of neighbouring rows and neighbouring columns, from a single cell up to the whole grid, and blocks in different places count separately. Values can be negative or zero.

Examples

count_submatrices([[0, 1, 0], [1, 1, 1], [0, 1, 0]], 0)  # returns 4
count_submatrices([[1, -1], [-1, 1]], 0)                 # returns 5
count_submatrices([[904]], 0)                            # returns 0

In the second example the five blocks are the two rows, the two columns and the whole grid.

Constraints

• The grid has 0 to 100 rows and 0 to 100 columns
• Values are between -1,000 and 1,000
• target is between -10**8 and 10**8