CF293B.Distinct Paths

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 (109 + 7).

你有一个 $n \times m$ 的矩形方格棋盘。其中一些方格已经被涂上了 $k$ 种颜色中的某一种。你需要将每个未涂色的方格涂上 $k$ 种颜色之一，使得从左上角方格到右下角方格的任意路径都不包含两个同色的方格。路径只能沿边相邻的方格移动，且只能向下或向右移动。

输出可能的涂色方案数对 $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.

第一行包含三个整数 $n$、$m$、$k$（$1 \leq n, m \leq 1000$，$1 \leq k \leq 10$）。接下来的 $n$ 行每行包含 $m$ 个整数，表示棋盘。其中第一行从左到右依次为棋盘最上方一行的 $m$ 个格子，第二行为次上方一行的 $m$ 个格子，依此类推。若某行中一个数字为 $0$，则对应格子未被涂色；否则该数字表示该格子的初始颜色，是一个介于 $1$ 到 $k$ 之间的整数。

将所有颜色以某种方式编号为 $1$ 至 $k$。

Print the number of possible paintings modulo 1000000007 (109 + 7).

输出可能的绘画方案数对 1000000007（即 $10^9 + 7$）取模的结果。