Counting Submatrices in the Hamster Den

In this problem, you are given a grid representing the hamster den, which is an ( n\times m ) matrix. Each cell in the grid is either intact (represented by 1) or damaged (represented by 0). The hamster wants to count the number of submatrices (i.e. contiguous blocks of cells) that contain no damaged cell.

A submatrix is defined by choosing a contiguous set of rows and a contiguous set of columns. For example, a (2\times3) matrix with all cells intact has:

• (6) submatrices of size (1\times1),
• (4) submatrices of size (1\times2),
• (2) submatrices of size (1\times3),
• (3) submatrices of size (2\times1),
• (2) submatrices of size (2\times2),
• (1) submatrix of size (2\times3),

resulting in a total of 18 submatrices.

Given that some cells in the matrix are damaged, your goal is to count only those submatrices that have all their cells intact. ( (i.e.,) every cell in the submatrix is 1 ()).

inputFormat

The first line of input contains two integers ( n ) and ( m ) representing the number of rows and columns of the matrix, respectively.\n\nEach of the next ( n ) lines contains ( m ) integers separated by spaces. Each integer is either 0 or 1, where 1 indicates an intact cell and 0 indicates a damaged cell.

outputFormat

Output a single integer representing the number of submatrices that contain no damaged cell.

sample

2 3
1 1 1
1 1 1

18