小 T 有一个 n×m 的矩阵 A,A 中的元素互不相同,可以构成一个 1∼nm 的排列。
如果一个序列是升序或者降序的,则称这个序列是好的。如果一个矩阵的每一行是好的,每一列也是好的,则称这个矩阵是好的。
求有多少个 A 的非空子矩阵是好的。
一个矩阵的非空子矩阵是指,选出行的一个非空子集与列的一个非空子集,既在这些行又在这些列的元素排成的新矩阵。可以发现,一个 n×m 的矩阵的非空子矩阵数为 (2n−1)(2m−1)。
输入格式
第一行两个整数 n,m,表示矩阵大小。
接下来 n 行,每行 m 个整数 Ai,j,表示矩阵 A 的元素。
输出格式
一行一个整数表示答案。
样例输入 1
2 2 1 3 2 4
样例输出 1
9
样例输入 2
2 3 2 3 1 4 5 6
样例输出 2
19
样例输入 3
3 4 4 5 10 8 9 6 3 2 11 7 12 1
样例输出 3
79
样例解释
样例 1 中所有子矩阵均满足要求。
样例 2 中只有子矩阵为整个矩阵,或第一行的所有数时不满足要求。
数据范围
对于所有数据,1≤n,m≤20,1≤Ai,j≤nm,保证 Ai,j 互不相同。
子任务 1(20 分):n,m≤10。
子任务 2(25 分):n,m≤15。
子任务 3(25 分):n,m≤18。
子任务 4(30 分):无特殊限制。