Problem E
Monotony

You are given an $r\! \times \! c$ grid. Each cell of this grid is filled with a number between $1$ and $r{\cdot }c$ inclusive, and each cell’s number is distinct.

Define a grid of numbers to be monotonic if each row and column is either increasing or decreasing (this can be different for each row or column).

Define a subgrid of the grid as follows: First choose some nonempty subset of the rows and columns. Next, take elements that lie in both the chosen rows and columns in the same order.

There are $(2^ r{-}1)(2^ c{-}1)$ nonempty subgrids of the given grid. Of these subgrids, count how many are monotonic.

Consider this grid:

There are nine $1{\times }1$ subgrids, nine $1{\times }2$’s, three $1{\times }3$’s, nine $2{\times }1$’s, nine $2{\times }2$’s, three $2{\times }3$’s, three $3{\times }1$’s, three $3{\times }2$’s, and one $3{\times }3$. They are all monotonic, for $9{+}9{+}3{+}9{+}9{+}3{+}3{+}3{+}1=49$ monotonic subgrids.

Input

Each test case will begin with a line with two space-separated integers $r$ and $c$ ($1\! \le \! r,c\! \le \! 20$), which are the dimensions of the grid.

Each of the next $r$ lines will contain $c$ space-separated integers $x$ ($1\! \le \! x\! \le \! r{\cdot }c$, all $x$’s are unique). This is the grid.

Output

Output a single integer, which is the number of monotonic subgrids in the given grid.

3 3
1 2 5
7 6 4
9 8 3

49

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

64