题目描述

就像人类喜欢玩跳房子游戏一样，农民约翰的奶牛也为自己发明了一种不同的游戏。奶牛跳房子是由体重近一吨的笨拙动物玩的，几乎总是以灾难告终，但令人惊讶的是，这并没有阻止奶牛几乎每天下午都尝试玩。

游戏是在一个$\red{R×}$$\red{C}$网格上进行的（$\red{2<=R<=100，}$$\red{2<=C<=100）}$，其中每个正方形都标有一个范围为$\red{1}$的整数。。$\red{K（}$$\red{1<=K<=R\times C）}$。奶牛从左上角的方块开始，通过一系列跳跃移动到右下角的方块，其中跳跃在且仅在以下情况下有效

$\red{1）}$ 跳转到一个标有与当前平方不同整数的平方，

$\red{2）}$ 您要跳转到的正方形至少比您所在的当前正方形低一行，并且

$\red{3）}$ 您要跳转到的正方形至少是当前正方形右侧的一列。

请帮助奶牛计算从左上角到右下角的有效跳跃的不同可能序列的数量。

输入格式

第一行包含整数$\red{R}$、$\red{C}$和$\red{K}$。

接下来的$\red{R}$行将分别包含$\red{C}$个整数，每个整数的范围为$\red{1...K}$

输出格式

输出从左上角跳转到右下角的不同方式的数量，$\red{mod~ }$$\red{100000007}$。

样例

输入样例

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

输出样例

5