题目描述

普通的跳格子游戏已经让作为体育健将的小 A 和他的同学们提不起兴趣了。他和同学们一起发明了一种新的跳格子的游戏。

他们在操场上画出了一个 N×M 大小的矩阵，矩阵的每个格子有一个不超过 T 的数字。在矩阵的任何一个点上，他们只能跳到该点右下角（不含正下方和正右侧）的任何值不等于当前点的位置上。

比如，小 A 当前跳到了 X,Y 点，那么接下来他可以跳跃到的点 X′,Y′ 要同时满足：X′>X，Y′>Y，且 X′,Y′ 点的数字和 X,Y 点的数字不相等。

请编程求出，按照上述规则，从 1,1 点跳到 N,M 点有多少种不同的方法。

输入

第 1 行读入 3 个整数 N,M,T。

接下来 N 行，每行读入 M 个不超过 T 的整数。

输出

输出从 1,1 点跳到 N,M 点的方法数，本题的跳跃方法数可能很多，你只需要输出跳跃方法数 mod$10^9$+7 的结果。

样例

输入

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

输出

2

输入

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

输出

5

输入

10 10 10
5 4 1 8 1 1 1 8 4 3
9 6 6 6 8 3 5 3 3 7
9 1 8 2 3 5 6 7 7 8
9 3 8 8 6 1 10 1 2 1
9 7 1 7 9 1 3 6 10 7
9 6 6 7 4 1 1 9 9 5
8 4 10 2 3 10 5 4 7 6
10 1 4 8 8 10 8 1 8 8
2 4 10 1 9 1 8 8 3 8
7 2 4 6 5 8 3 3 8 10

输出

8758

说明

样例 1 解释

有 2 条可行路线。

路线 1 经过的点：1,1−2,2−3,4。

路线 2 经过的点：1,1−3,4。

数据范围

对于 100% 的数据，2≤N,M≤100，1≤T≤N×M。