A kiln fires a mosaic represented as a grid of R rows and C columns. A cell holds 1 if its tile survived firing intact and 0 otherwise. An inspector counts inspection squares: an inspection square of side s is any axis-aligned s-by-s block whose cells are all 1 (for every s >= 1).
Determine the total number of inspection squares of all sizes. A single intact tile counts as one inspection square of side 1; larger all-intact blocks count additionally.
Input format
Line 1: two integers R and C.
Next R lines: each contains C integers, each 0 or 1.
Output format
A single integer: the total number of all-1 square sub-blocks of every size.
Constraints
- 1 <= R <= 100
- 1 <= C <= 100
- Each cell is 0 or 1.
- The answer is guaranteed to fit in a signed 64-bit integer.