AT_abc293_c.[ABC293C] Make Takahashi Happy

有一个 $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)$）上写的整数都互不相同，那么高桥君会感到高兴。请输出作为高桥君移动路径的所有可能方案中，使高桥君高兴的方案数。

输入以如下格式从标准输入给出。

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

请输出答案。

限制条件

• $2 \leq H, W \leq 10$
• $1 \leq A_{i, j} \leq 10^9$
• 输入均为整数

样例解释 1

高桥君的所有可能移动路径如下，共有 $6$ 种。

• $(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$ 种，共 $3$ 个。

样例解释 2

在这个例子中，无论高桥君选择哪条路径，他都会高兴。

由 ChatGPT 4.1 翻译