问题描述

有一个 $H$ 行 $W$ 列的网格。对于满足 $1 \leq i \leq H$ 和 $1 \leq j \leq W$ 的整数 $i$ 和 $j$，位于从上往下数第 $i$ 行、从左往右数第 $j$ 列的方块（用 $(i, j)$ 表示）上写着整数 $A_{i, j}$。

高桥目前位于 $(1,1)$。从现在开始，他重复以下操作，即从当前方块向右边或下边的相邻方块移动，直到达到 $(H, W)$。在移动时，不允许超出网格范围。

如果高桥所经过方块上的整数（包括初始方块 $(1, 1)$ 和最后方块 $(H, W)$）各不相同，他将感到高兴。计算使他感到高兴的可能路径的数量。

约束条件

• $2 \leq H, W \leq 10$
• $1 \leq A_{i, j} \leq 10^9$
• 输入中的所有值都是整数。

输入

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

$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}$

输出

输出答案。

示例输入 1

3 3
3 2 2
2 1 3
1 5 4

示例输出 1

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$，因此他会感到高兴。

因此，上述第三、第五和第六条路径会使他感到高兴。

示例输入 2

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

示例输出 2

48620

在这个例子中，任何可能的路径都会使他感到高兴。