Bob's House Site

Bob is a well known builder. He bought a piece of land and wants to build a house on it, but the land does not have the same elevation everywhere.

The land is a rectangle divided into $N \times M$ square cells, $N$ rows by $M$ columns. Bob's house is also a rectangle. Its sides are parallel to the sides of the land and its corners meet corners of cells. Every cell the house covers must have the same elevation, otherwise the house collapses.

Count the number of ways Bob can place his house. A house that covers a single cell counts as one way.

The first line contains two integers $N$ and $M$ ($1 \le N, M \le 1000$).

Each of the next $N$ lines contains $M$ integers. The $j$-th number $a_{ij}$ is the elevation of the cell in row $i$, column $j$ ($1 \le a_{ij} \le 10^9$).

The input is large, so use a fast reading method. In C++ use scanf instead of cin, in Java use BufferedReader instead of Scanner.

Print the number of ways on one line.

In the first example, the rectangle with opposite corners (0,0) and (1,1) and the rectangle with opposite corners (0,0) and (0,2) both sit at elevation 2, and the rectangle with opposite corners (2,0) and (2,2) and the rectangle with opposite corners (1,2) and (2,2) both sit at elevation 1. The first number in the parentheses is the row and the second is the column, counted from 0.