P99720

Cow Hopscotch

难度 6 级 动态规划入门 线性 线段树
讨论 统计 0通过 0提交 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

与人类喜欢玩跳格子游戏类似,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

来源

USACO

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交