Count the Rugs That Fit

A tiled floor is mapped as a list of strings of equal length, one per row: '1' is a good tile and '0' is a cracked one. A rug covers a rectangle of whole tiles, with its sides along the rows and columns, and it may only lie on good tiles.

Write count_rectangles(floor) that returns how many different rectangles of good tiles there are: every choice of a block of neighbouring rows and a block of neighbouring columns whose tiles are all '1' counts once, from a single tile up to the largest.

Examples

count_rectangles(['11',
                  '11'])     # returns 9
count_rectangles(['101',
                  '111'])    # returns 10
count_rectangles(['0'])      # returns 0

The 2 by 2 floor holds four single tiles, two 1 by 2 rugs, two 2 by 1 rugs and one 2 by 2 rug: 9 in all.

Constraints

• 1 to 150 rows and 1 to 150 columns.
• The answer can be over a hundred million, far too many rectangles to look at one by one.