题目描述

Just like humans enjoy playing the game of Hopscotch, Farmer John's cows have invented a variant of the game for themselves to play. Being played by clumsy animals weighing nearly a ton, Cow Hopscotch almost always ends in disaster, but this has surprisingly not deterred the cows from attempting to play nearly every afternoon.

The game is played on an $R$ by $C$ grid $(2 <= R <= 100,$ $2 <= C <= 100)$, where each square is labeled with an integer in the range $1...K (1 <= K <= R * C)$. Cows start in the top-left square and move to the bottom-right square by a sequence of jumps, where a jump is valid if and only if:

1. You are jumping to a square labeled with a different integer than your current square,

2. The square that you are jumping to is at least one row below the current square that you are on, and

3. The square that you are jumping to is at least one column to the right of the current square that you are on.

Please help the cows compute the number of different possible sequences of valid jumps that will take them from the top-left square to the bottom-right square.

输入格式

The first line contains the integers $R, C,$ and $K$. The next $R$ lines will each contain $C$ integers, each in the range $1..K$.

输出格式

Output the number of different ways one can jump from the top-left square to the bottom-right square, mod $1000000007$.

题目大意

牛跳房子游戏在一个 $R \times C$ 的网格中进行，每个格子上有一个 $1 \cdots K$ 的数字$( 1 \leq K \leq R \times C )$。

牛从网格的左上角出发，跳到右下角。一次跳跃是合法的，当且仅当满足以下的所有条件：

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

现在请你求出：从左上角跳到右下角的合法跳跃的方案数量。

输入格式：第一行输入三个数字， $R , C , K$ .接下来 $R$ 行每行输入 $C$ 个数字来描述游戏地图。保证每个数字都在 $1 \leq K$ 的范围内。

输出格式：输出总方案数 $\bmod$ $10^9+7$ 的结果。

Translated by @StudyingFather

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

5