题目限制

1000 ms 128 M

题目描述

牛牛和小伙伴们高兴的猜完了数字，就要进入牛牛生日的最后一个环节了，大家期待已久的——飞行棋。众所周知，飞行棋每个人会执不同颜色的飞行棋子，由于人数众多，牛牛的飞行棋盘和正常的有点不一样，是一个n*m大小的棋盘，游戏开始时每个人可以在棋盘的任意位置放上自己的若干个棋子，也可以不放，当然每个位置只能放一个，之后大家齐心协力 填满 这个棋盘，唯一的要求是在 任意一条 从左上角到右下角的路线上不能出现相同的棋子，这里的路线只能向下和向右走，他们想知道总共有多少种方案数，很显然方案数可能有很多，所以只需要你告诉他们方案数对1000000007(10^9+7)取模的结果即可。

输入格式

第一行三个整数n，m，k，k表示人数。
接下来n行，每行m个用空格隔开的数字，数字1-k表示这个位置放了对应编号人的棋子，0表示这个位置没放棋子。

输出格式

一个数表示方案数。

数据范围

对于30%的数据，n,m<=3，k<=5。
对于另外10%的数据，初始棋盘没有放任何棋子。
对于100%的数据，0<n,m,k<=10。

输入样例

样例一

2 2 4
0 0
0 0

样例二

3 3 5
0 0 0
0 0 0
4 0 0

样例三

3 3 5
0 0 0
0 0 1
0 0 0

输出样例

样例一

48

样例二

24

样例三

24