Little T has an $n \times m$ matrix $A$, where the elements of $A$ are distinct and form a permutation of $1 \sim nm$.

A sequence is called "good" if it is either strictly increasing or strictly decreasing. A matrix is called "good" if every row is good and every column is also good.

Find the number of non-empty submatrices of $A$ that are good.

A non-empty submatrix of a matrix is formed by selecting a non-empty subset of rows and a non-empty subset of columns, and taking the elements that lie in both these rows and these columns to form a new matrix. It can be observed that the number of non-empty submatrices of an $n \times m$ matrix is $(2^n-1)(2^m-1)$.

Input

The first line contains two integers $n$ and $m$, representing the size of the matrix.

The next $n$ lines each contain $m$ integers $A_{i,j}$, representing the elements of matrix $A$.

Output

Output a single integer representing the answer.

Examples

Input 1

2 2
1 3
2 4

Output 1

9

Input 2

2 3
2 3 1
4 5 6

Output 2

19

Input 3

3 4
4 5 10 8
9 6 3 2
11 7 12 1

Output 3

79

Note

In Example 1, all submatrices satisfy the requirements.

In Example 2, only the submatrix consisting of the entire matrix or the submatrix consisting of all numbers in the first row do not satisfy the requirements.

Constraints

For all test cases, $1 \leq n, m \leq 20$, $1 \leq A_{i,j} \leq nm$, and it is guaranteed that all $A_{i,j}$ are distinct.

Subtask 1 (20 points): $n, m \leq 10$.

Subtask 2 (25 points): $n, m \leq 15$.

Subtask 3 (25 points): $n, m \leq 18$.

Subtask 4 (30 points): No special constraints.