Cow Hopscotch (Gold)

题目描述

就像人类喜欢玩跳房子一样，农夫约翰的奶牛们也发明了一个变种游戏供自己玩。由于参与游戏的是笨拙且体重接近一吨的动物，奶牛跳房子几乎总是以灾难告终，但这竟然并没有阻止奶牛们几乎每天下午都尝试玩这个游戏。\n游戏在一个 $R$ 行 $C$ 列的网格上进行（$2 \le R \le 750$, $2 \le C \le 750$），每个格子都标有一个 $1..K$ 范围内的整数（$1 \le K \le R*C$）。奶牛从左上角的格子出发，通过一系列跳跃移动到右下角的格子。一次跳跃当且仅当满足以下条件时才是合法的：\n1）你要跳到的格子上的整数与当前格子上的整数不同，\n2）你要跳到的格子至少在当前格子的下一行（行号更大），并且\n3）你要跳到的格子至少在当前格子的右侧一列（列号更大）。\n请帮助奶牛计算：从左上角格子跳到右下角格子，合法跳跃序列共有多少种不同的可能。

输入格式

第一行包含整数 $R$, $C$, $K$。\n接下来的 $R$ 行每行包含 $C$ 个整数，每个都在 $1..K$ 的范围内。

输出格式

输出从左上角格子跳到右下角格子的不同方法数，对 $1000000007$ 取模。

4 4 4\n1 1 1 1\n1 3 2 1\n1 2 4 1\n1 1 1 1

5

提示

[题目来源：Nick Wu, 2015]

标签: USACO|2015|Gold

来源

USACO|2015|Gold