3046: Distinct Paths
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：
题目描述
小美有一个n*m的木板，一些块已经被涂上给出的k种颜色中的一种。你需要把每个没涂色的块涂色使得从左上角到右下角的每条路径都不会经过两个颜色一样的块。路径只能向右或向下走。 输出答案%1000000007。
输入
第一行3个整数n,m,k。 接下来n行，每行m个整数表示木板，其中第一行表示最上的m块，每行第一个数表示最左列的块。 对于每个整数，如果为0，表示未涂色，否则表示涂上颜色的编号。
输出
一个答案表示方案数。
样例输入 复制
2 2 4
0 0
0 0样例输出 复制
48提示
【数据规模和约定】10%的数据满足n=130%的数据满足n<=2
1<=n,m<=1000,1<=k<=10