seuOJ470 - 不同的路径

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：迎新赛, 2023

题目描述

给定一个 $n\times m$ 的矩形色板，有 $k$ 种不同的颜料，有些格子已经填上了某种颜色，现在需要将其他格子也填上颜色，使得从左上角到右下角的任意路径不会包含任何两个相同颜色的单元格。路径只能沿着相邻的格子，且只能向下或者向右。

计算所有可能的方案数，结果对 $1000000007 (10^9 + 7)$取模。

输入格式

第一行，三个整数 $n, m, k (1 \le n, m \le 1000, 1 \le k \le 10)$。 接下来 $n$ 行，每行包含 $m$ 个整数 $a_{n,m}(0\le a_{n,m} \le k)$，表示颜色。其中 $0$ 表示未涂色，非 $0$ 表示颜色的编号， 颜色编号为 $1$ 到 $k$。

输出格式

一行，一个整数，表示涂色方案对 $1000000007 (10^9 + 7)$ 取模的结果。

样例

输入样例1

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

输出样例1

4096

输入样例2

2 2 4
0 0
0 0

输出样例2

48

输入样例3

2 2 4
1 2
2 1

输出样例3

0