题目描述

小 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}$互不相同。