发现 \(n, m\) 的数据范围是假的，因为每一步一个颜色最多也就 \(k\le 10\) 种颜色，所以当 \(n + m - 1 > k\) 时一定无解。
接下来发现这个数据范围挺小的，考虑状压，设 \(f_{x, y}\) 为走到 \((x, y)\) 点所用的颜色的集合，其可以由 \(f_{x - 1, y}, f_{x, y - 1}\) 推来。
然后就可以枚举还未选过的颜色，选一个填到 \((x, y)\)，同时更新 \(f_{x, y}\)，因为多用了一个颜色，然后继续往后推一步步得到答案，推的顺序可以一行一行推。
这样朴素的搜索肯定是过不了的，考虑优化：
- 若 \(k - \operatorname{popcount}(f_{x, y})<(n - x) + (m - y) + 1\)（此时 \((x, y)\) 还没有选颜色，\(\operatorname{popcount(x)}\) 代表 \(x\) 二进制下 \(1\) 的个数），即剩余的颜色已经不足以继续填到终点，方案数肯定为 \(0\)。
- 若在同一方格的染色过程中，\(a, b\) 两种颜色都是第一次在图中出现，那么 \(a,b\) 对应的贡献一定是相同的，所以对于只需算出 \(a\) 的贡献 \(ret\)，\(b\) 的贡献也为 \(ret\) 不用再次计算。
// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: B. Distinct Paths
// Contest: Codeforces - Croc Champ 2013 - Round 2
// URL: https://codeforces.com/problemset/problem/293/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int N = 10 + 5;
int n, m, k;
int col[N][N], f[N][N];
int ud[N];
const int mod = 1e9 + 7;
int dfs(int x, int y) {
if (y > m) {
x++, y = 1;
}
if (x > n) {
return 1;
}
int s = f[x - 1][y] | f[x][y - 1];
int cnt = k;
for (int i = 1; i <= k; i++) {
if ((s >> (i - 1)) & 1) {
cnt--;
}
}
if (cnt < (n - x) + (m - y) + 1) {
return 0;
}
int ret = -1, ans = 0;
for (int i = 1; i <= k; i++) {
if ((col[x][y] && col[x][y] != i) || ((s >> (i - 1)) & 1)) {
continue;
}
f[x][y] = s | (1 << (i - 1));
if (! ud[i]) {
ud[i] = 1;
if (ret == -1) {
ret = dfs(x, y + 1);
}
ans = (ans + ret) % mod;
ud[i] = 0;
}
else {
ans = (ans + dfs(x, y + 1)) % mod;
}
}
return ans;
}
int main() {
scanf("%d%d%d", &n, &m, &k);
if (n + m - 1 > k) {
printf("0");
return 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &col[i][j]);
ud[col[i][j]] = 1;
}
}
printf("%d\n", dfs(1, 1));
return 0;
}