Distinct Paths

【问题描述】 给定一个 n*m 的矩形色板，有 k 种不同的颜料，有些格子已经填上了某种颜色，现在 需要将其他格子也填上颜色，使得从左上角到右下角的任意路径经过的格子都不会出现两种 及以上相同的颜色。路径只能沿着相邻的格子，且只能向下或者向右。 计算所有可能的方案，结果对 1000000007 (10^9 + 7)求模。 【输入数据】 第一行，三个整数 n, m, k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10)； 接下来 n 行，每行包含 m 个整数，表示颜色。其中 0 表示未涂色，非 0 表示颜色的编号， 颜色编号为 1 到 k。 【输出数据】 一行，一个整数，表示涂色方案对 1000000007 (10^9 + 7)求模的结果。 由 @hicc0305 提供翻译

You have a rectangular $ n×m $ -cell board. Some cells are already painted some of $ k $ colors. You need to paint each uncolored cell one of the $ k $ colors so that any path from the upper left square to the lower right one doesn't contain any two cells of the same color. The path can go only along side-adjacent cells and can only go down or right. Print the number of possible paintings modulo $ 1000000007 $ $ (10^{9}+7) $ .

The first line contains three integers $ n,m,k $ $ (1<=n,m<=1000,1<=k<=10) $ . The next $ n $ lines contain $ m $ integers each — the board. The first of them contains $ m $ uppermost cells of the board from the left to the right and the second one contains $ m $ cells from the second uppermost row and so on. If a number in a line equals 0, then the corresponding cell isn't painted. Otherwise, this number represents the initial color of the board cell — an integer from 1 to $ k $ . Consider all colors numbered from 1 to $ k $ in some manner.

Print the number of possible paintings modulo $ 1000000007 $ $ (10^{9}+7) $ .

2 2 4
0 0
0 0

48

2 2 4
1 2
2 1

0

5 6 10
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

3628800

2 6 10
1 2 3 4 5 6
0 0 0 0 0 0

4096