CF293B Distinct Paths

你有一个 $n \times m$ 的矩形棋盘。部分格子已经被涂上了 $k$ 种颜色中的某一种颜色。你需要为每个未上色的格子涂上 $k$ 种颜色中的一种，使得任意一条从左上角到右下角的路径都不包含两个相同颜色的格子。这条路径只能沿着相邻的格子走，并且只能向下或向右移动。 请输出所有可能的涂色方案数，答案对 $1000000007$（$10^9+7$）取模。

第一行包含三个整数 $n, m, k$，满足 $1 \leq n, m \leq 1000$，$1 \leq k \leq 10$。接下来 $n$ 行，每行包含 $m$ 个整数，表示棋盘的状态。每个数字为 $0$ 表示该格子未涂色，若为非零整数 $c$，则表示该格子已经被涂上 $k$ 种颜色中的第 $c$ 种。 全部颜色以 $1$ 到 $k$ 的编号顺序标记。

输出所有可能的涂色方案数，对 $1000000007$ 取模。

由 ChatGPT 5 翻译