题目描述
小 T 有一个 $n \times m$ 的矩阵 $A$,$A$ 中的元素互不相同,可以构成一个 $1$ ~ $ nm$的排列。
如果一个序列是升序或者降序的,则称这个序列是好的。如果一个矩阵的每一行是好的,每一列也是好的,则称这个矩阵是好的。
求有多少个 $A$ 的非空子矩阵是好的。
一个矩阵的非空子矩阵是指,选出行的一个非空子集与列的一个非空子集,既在这些行又在这些列的元素排成的新矩阵。可以发现,一个 $n \times m$ 的矩 阵的非空子矩阵数为 $(2^n-1)(2^m-1)$。
输入格式
从文件 matrix.in 中读入数据。
第一行两个整数 $n,m$,表示矩阵大小。
接下来 $n$ 行,每行 $m$ 个整数 $A_{i,j}$,表示矩阵 $A$ 的元素。
输出格式
输出到文件 matrix.out 中。
一行一个整数表示答案。
样例 1
样例 1 输入
2 2
1 3
2 4
样例 1 输出
9
样例 1 解释
所有子矩阵均满足要求。
样例 2
样例 2 输入
2 3
2 3 1
4 5 6
样例 2 输出
19
样例 2 解释
只有子矩阵为整个矩阵,或第一行的所有数时不满足要求。
样例 3
样例 3 输入
3 4
4 5 10 8
9 6 3 2
11 7 12 1
样例 3输出
79
样例 4
样例 4 输入
10 10
77 62 56 97 96 29 48 93 92 91
90 89 63 87 86 85 39 22 5 81
80 79 78 100 76 75 27 73 72 1
70 69 68 31 66 65 64 52 99 61
60 59 58 57 98 55 54 36 53 2
50 49 94 47 46 45 44 43 8 41
40 84 38 37 28 35 34 33 14 67
30 95 82 74 26 25 24 23 83 21
20 19 18 17 16 15 32 13 12 11
10 9 42 7 6 88 4 3 51 71
样例 4 输出
15613
数据范围与提示
对于所有数据,$n,m \le 20$ ,$1 \le A_{i,j} \le nm$ ,保证 $A_{i,j}$互不相同。