Strawberry Field Potential

Mirko is troubled by finding suitable land to plant strawberries. His land is represented by an \(N \times M\) matrix. Each cell in the matrix is either suitable (represented by 1) or unsuitable (represented by 0) for growing strawberries. A rectangular submatrix is called a suitable rectangle if all of its cells are 1.

The potential value of a cell is defined as the number of suitable rectangles that contain that cell. Equivalently, if a suitable rectangle has dimensions \(h \times w\) (i.e. area \(h\cdot w\)), then it contributes \(h\cdot w\) to the sum (since each of its \(h\cdot w\) cells gets counted once). The overall answer is the sum of the potential values of all cells, which is equal to the sum of the areas of all suitable rectangles.

Task: Given the matrix representing Mirko's land, compute the sum of the areas of all suitable rectangles.

Hint: One efficient approach is to use dynamic programming. First, for each cell, compute the number of consecutive ones to the left (including the cell itself). Then, for each cell treated as the bottom-right corner of a rectangle, iterate upward to update the minimum contiguous ones (which gives the maximum width for a suitable rectangle ending at that cell) and accumulate the contribution. For a fixed bottom-right cell at \((i,j)\), if for a top candidate row \(k\) (with \(0 \le k \le i\)) the minimum continuous ones is \(w\), then all rectangles with bottom row \(i\) and top row \(k\) that end at \(j\) can extend in width from 1 to \(w\) (and their area is \((i-k+1)\times (\text{width})\)). Thus, add \((i-k+1) \times \frac{w(w+1)}{2}\) to the answer.

The input and output format are described below.

inputFormat

The first line contains two integers \(N\) and \(M\) \( (1 \le N,M \le 100)\), representing the number of rows and columns.

The following \(N\) lines each contain \(M\) integers. Each integer is either 0 or 1, where 1 indicates a cell that is suitable for growing strawberries and 0 indicates an unsuitable cell.

outputFormat

Output a single integer, the sum of the potential values of all cells in the matrix, which is equal to the sum of the areas of all suitable rectangles.

sample

2 2
1 1
1 1

16