让高桥开心

题目描述

有一个 $H$ 行 $W$ 列的网格。 对于满足 $1 \le i \le H$、$1 \le j \le W$ 的整数 $i, j$，从上数第 $i$ 行、从左数第 $j$ 列的格子（记为 $(i, j)$）上写有整数 $A_{i, j}$。

高桥现在位于 $(1, 1)$。从现在起，他重复移动到当前格子右边或下边的相邻格子，直到到达 $(H, W)$。移动时不能走出网格。

如果他所经过的格子（包括起点 $(1, 1)$ 和终点 $(H, W)$）上写有的整数各不相同，高桥就会开心。 求能让他开心的路径条数。

输入格式

输入按以下格式从标准输入给出：

$H$ $W$
$A_{1, 1}$ $A_{1, 2}$ $\ldots$ $A_{1, W}$
$A_{2, 1}$ $A_{2, 2}$ $\ldots$ $A_{2, W}$
$\vdots$
$A_{H, 1}$ $A_{H, 2}$ $\ldots$ $A_{H, W}$

输出格式

输出答案。

样例

3 3
3 2 2
2 1 3
1 5 4

3

共有六条可能的路径：

$(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3)$：经过格子上的整数为 $3, 2, 2, 3, 4$，所以他不开心。

$(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)$：经过格子上的整数为 $3, 2, 1, 3, 4$，所以他不开心。

$(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)$：经过格子上的整数为 $3, 2, 1, 5, 4$，所以他开心。

$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)$：经过格子上的整数为 $3, 2, 1, 3, 4$，所以他不开心。

$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)$：经过格子上的整数为 $3, 2, 1, 5, 4$，所以他开心。

$(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3)$：经过格子上的整数为 $3, 2, 1, 5, 4$，所以他开心。

因此，上面描述的第 3、5、6 条路径能让他开心。

10 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

48620

在本例中，所有可能的路径都能让他开心。

数据范围

• $2 \le H, W \le 10$
• $1 \le A_{i, j} \le 10^9$
• 输入中的所有值均为整数