1953. 牛跳房子

【题目描述】

就像有些人喜欢玩Hopscotch游戏一样，农夫约翰的奶牛们发明了这个游戏的一个变种，自己玩。重达一吨笨拙动物玩Cow Hopscotch，几乎总是以不幸告终，但令人惊讶的是，这无法阻止奶牛们几乎每天下午都玩儿这个游戏。

该游戏有一个R*C（2 < = R≤750，2＜＝C <= 750）的网格，其中每一个格子里有一个[1..K]里的整数（1<=K<=R*C)。奶牛们从左上方开始，通过连续的跳跃移动到右下角，当且仅当满足以下条件，跳跃才是有效的：

1）你可以跳到一个与当前数值不同的方格上，

2）你要从当前正确的方块至少向下跳一行，

3）你要从当前正确的方块至少向右跳一列。

//即可以跳到严格右下方且数值与当前格不同的格子。

请帮助奶牛们计算他们从左上到右下方有多少种不同的有效跳跃序列方案。

【输入格式】

第一行包含三个整数R、C和K

下面有R行，每行都包含C个整数(每个都在[1..K]中)。

【输出格式】

输出一个数，即可以从左上连续跳跃至右下方的不同的方案数（mod 1000000007)。

【样例输入】

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

【样例输出】

5

【提示】

在此键入。

【来源】

在此键入。