飞行棋

题目限制

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

信息

ID
1063
难度
(无)
分类
(无)
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
1
上传者