Good 2×2 Submatrices

Problem Description

Little A has an $n \times m$ matrix $A$.

Little A calls a $2 \times 2$ matrix $D$ good if and only if $D_{1,1} \times D_{2,2} = D_{1,2} \times D_{2,1}$, where $D_{i,j}$ denotes the element in the $i$-th row and $j$-th column of $D$.

Little A wants to know how many good submatrices $A$ contains.

Input Format

The first line contains two positive integers $n$ and $m$. The next $n$ lines each contain $m$ integers $A_{i,1}, A_{i,2}, \ldots, A_{i,m}$.

Output Format

One line: one integer, the number of good submatrices in $A$.

Sample Input

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

Sample Output

2

Sample Explanation

In the given $3 \times 4$ matrix, there are $(3-1) \times (4-1) = 6$ possible $2 \times 2$ submatrices. We check each against $D_{1,1} \times D_{2,2} = D_{1,2} \times D_{2,1}$.

• The submatrix with top-left corner at row $1$, column $1$ is $\begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix}$; we get $1 \times 4 = 4$ and $2 \times 2 = 4$, equal, so it is good.
• The submatrix with top-left corner at row $1$, column $2$ is $\begin{bmatrix} 2 & 1 \\ 4 & 2 \end{bmatrix}$; we get $2 \times 2 = 4$ and $1 \times 4 = 4$, equal, so it is also good.

The other four submatrices fail the equality condition, so there are $2$ good submatrices in total.

Constraints

For all test points, $1 \le n \le 500$, $1 \le m \le 500$, $-100 \le A_{i,j} \le 100$.