题目描述

就像人类喜欢跳格子游戏一样，FJ 的奶牛们发明了一种新的跳格子游戏。虽然这种接近一吨的笨拙的动物玩跳格子游戏几乎总是不愉快地结束，但是这并没有阻止奶牛们在每天下午参加跳格子游戏。

游戏在一个 $R\times C$ 的网格上进行，每个格子有一个取值在 $1\sim k$ 之间的整数标号，奶牛开始在左上角的格子，目的是通过若干次跳跃后到达右下角的格子，当且仅当格子 A 和格子 B 满足如下条件时能从格子 A 跳到格子 B：

1. B 格子在 A 格子的严格右方（B 的列号严格大于 A 的列号）；
2. B 格子在 A 格子的严格下方（B 的行号严格大于 A 的行号）；
3. B 格子的标号和 A 格子的标号不同。

请你帮助奶牛计算出从左上角的格子到右下角的格子一共有多少种不同的方案。

输入格式

输入的第一行包含三个整数 $R,C$ 和 $K$。

接下来 $R$ 行，每行包含 $C$ 个整数，每个数在 $1\sim K$ 之间。

输出格式

一行，代表有多少种不同的方案，由于答案很大，请输出答案对 $10^9+7$ 取模的结果。

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

5

数据规模与约定

对于 $100\%$ 的数据，$2\le R,C\le 750$，$1\le K\le RC$。

题目来源

USACO February 2015 Contest Gold T1