Description

The adorable "Created equal" is a little hamster, and of course a little hamster has a hamster nest.

The nest is an $n\times m$ matrix with $n$ rows and $m$ columns. The little hamster wants to know how many submatrices this matrix has.

For example, for a $2\times 3$ matrix, there are $6$ submatrices of size $1\times 1$, $4$ of size $1\times 2$, $2$ of size $1\times 3$, $3$ of size $2\times 1$, $2$ of size $2\times 2$, and $1$ of size $2\times 3$, so in total there are $6+4+2+3+2+1=18$ submatrices.

However, some cells in the nest are damaged. Now the little hamster wants to know how many submatrices contain no damaged cells.

Input Format

The first line contains two positive integers $n$ and $m$, denoting the number of rows $n$ and columns $m$ of the nest.

Then follow $n$ lines, each containing $m$ numbers. Each number is either $0$ or $1$. A $0$ means the cell is damaged; otherwise the cell is intact.

Output Format

Output a single integer: the number of submatrices that are undamaged.

3 4
1 1 1 1
1 0 1 1
1 1 0 1

26

Hint

The time limit is $2\text{s}$ and the memory limit is $256\text{M}$. Since the new judge is close in speed to the NOIP judge, please be mindful of the impact of constant factors.

Translated by ChatGPT 5