P4825 [USACO15FEB] Cow Hopscotch S

题目描述

与人类喜欢玩跳格子游戏类似，Farmer John 的奶牛们也发明了自己的版本。游戏在一个 $R \times C$ 的网格上进行（$2 \leq R,C \leq 100$），每个格子标有 $1 \ldots K$ 的整数（$1 \leq K \leq R \times C$）。奶牛从左上角出发，通过一系列有效跳跃到达右下角。跳跃被定义为有效当且仅当满足以下条件：

1. 目标格子与当前格子的数字不同
2. 目标格子位于当前格子下方至少一行
3. 目标格子位于当前格子右侧至少一列

请计算从左上角到右下角的不同有效跳跃路径总数。

输入格式

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

输出格式

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

输入输出样例 1

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

5