题目描述

强哥是一位狂热的宝石收藏家，他最近发现了一张神秘的藏宝图，图上标记了一个 $H \times W$ 的宝石矿洞。每个矿格 $(i, j)$ 中都埋藏着一颗独特的宝石，宝石的种类用数字 $A_{i,j}$ 表示。

强哥决定从矿洞的入口 $(1, 1)$ 出发，挖掘一条路径到达出口 $(H, W)$。由于矿洞结构特殊，他只能向右或向下挖掘。

但强哥有个怪癖——他拒绝在单次探险中收集两颗相同种类的宝石，否则他会觉得这次探险不够完美。

你的任务是计算：强哥有多少种不同的挖掘路径，能让他收集到的所有宝石种类都不重复？

输入格式

第一行包含两个整数 $H$ 和 $W$，表示矿洞的行数和列数。

接下来 $H$ 行，每行包含 $W$ 个整数，表示每个矿格中的宝石种类 $A_{i,j}$。

输出格式

输出一个整数，表示满足条件的挖掘路径总数。

样例

输入样例 1

3 3  
3 2 2  
2 1 3  
1 5 4

输出样例 1

3

数据范围

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