P3120 [USACO15FEB] Cow Hopscotch G

题目描述

与人类喜欢玩跳格子游戏类似，Farmer John 的奶牛们也发明了自己的游戏版本。尽管体重接近一吨的笨拙动物玩这个游戏几乎总会以灾难收场，但这意料之外地没有阻止奶牛们每天下午尝试玩耍的热情。

游戏在一个 $R$ 行 $C$ 列的网格上进行（$2 \leq R, C \leq 750$），每个格子标有 $1$ 到 $K$ 的整数（$1 \leq K \leq R \times C$）。奶牛从左上角的格子出发，通过一系列合法跳跃到达右下角的格子。一次跳跃被定义为合法当且仅当满足以下条件：

1. 目标格子的标签数字与当前格子不同；
2. 目标格子所在行至少比当前格子多一行；
3. 目标格子所在列至少比当前格子多一列。

请帮助奶牛计算从左上角到右下角的不同合法跳跃序列总数。

输入格式

第一行包含三个整数 $R$, $C$, $K$。

接下来 $R$ 行，每行包含 $C$ 个整数，表示网格的标签（范围 $1$ 到 $K$）。

输出格式

输出从左上角到右下角的不同跳跃路径数量，结果对 $1000000007$ 取模。

输入输出样例 1

4 4 4 
1 1 1 1 
1 3 2 1 
1 2 4 1 
1 1 1 1

5