2807 「COCI 2014.11.08」BOB

译自 COCI 2014.11.08 T4. BOB

Bob 是一位著名的建筑家，他买下了一座岛屿 ~~（真有钱）~~ 并想在岛上盖房子。不幸的是，这座岛屿地势崎岖。岛屿可以用一个 $N$ 行 $M$ 列的矩阵来表示。Bob 的房子也是矩形的，并且每条边都平行于岛屿的边。为了避免房子塌陷，Bob 需要在海拔相等的地方建造房子。
你需要帮 Bob 计算他有多少种建造房子的方式。

简要题意 $\ $ 给你一个 $N$ 行 $M$ 列的矩阵 $C$，$C$ 的每个格子 $C_{i,j}$ 都有一个权值 $a_{i,j}$。对于 $C$ 的所有子矩阵，当且仅当子矩阵内的所有格子权值相等，我们称这个子矩阵是「合法」的。特别地，$C$ 是 $C$ 的子矩阵。求 $C$ 的「合法」子矩阵个数。

第一行两个正整数，代表 $N,M$ $(1 \leq N,M \leq 1000)$。
接下来 $N$ 行，每行 $M$ 个正整数。第 $i$ 行的第 $j$ 个数 $a_{i,j}$ $(1\leq a_{i,j}\leq 10^9)$ 代表岛屿的第 $i$ 行第 $j$ 个格子的海拔。
由于输入数据可能很大，请使用读入优化。

一行一个正整数，代表方案数。

房子的对角可以分别在 * $(0,0),(1,1)$； * $(0,0),(0,2)$； * $(2,0),(2,2)$； * $(2,1),(3,1)$。

（$(0,0)$为左上角）

对于 $20\%$ 的数据，$N,M\leq 50$；
对于 $60\%$ 的数据，$N,M\leq 500$；
对于 $100\%$ 的数据，$1\leq N,M\leq 1000, 1\leq a_{i,j}\leq 10^9$。