← 返回题目列表

Codeforces · 293/B

B. 不同的路径

中文机器翻译题面 查看原题

您有一块矩形 n × m 单元板。有些单元格已经涂上了 k 种颜色。您需要将每个未着色的单元格绘制为 k 种颜色中的一种,以便从左上方块到右下方块的任何路径不包含任何两个相同颜色的单元格。该路径只能沿着侧边相邻的单元格走,并且只能向下或向右走。

打印可能的绘画数量以 1000000007 (109 + 7) 为模。

输入

第一行包含三个整数 n、m、k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10)。接下来的 n 行每行包含 m 个整数——棋盘。第一个包含棋盘上从左到右的 m 个最上面的单元格,第二个包含第二个最上面行的 m 个单元格,依此类推。如果一行中的数字等于 0,则不会绘制相应的单元格。否则,这个数字代表棋盘单元的初始颜色——一个从 1 到 k 的整数。

以某种方式考虑从 1 到 k 编号的所有颜色。

输出

打印可能的绘画数量以 1000000007 (109 + 7) 为模。

示例

输入 #1

2 2 4
0 0
0 0

输出 #1

48

输入 #2

2 2 4
1 2
2 1

输出 #2

0

输入 #3

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

输出 #3

3628800

输入#4

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

输出#4

4096