题目描述

译自 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$ 个格子的海拔。
由于输入数据可能很大，请使用读入优化。

输出格式

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

5 3
2 2 2
2 2 1
1 1 1
2 1 2
1 2 1

27

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

36

数据范围与提示

对于 $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$。