题目描述

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

计算可能的方案数量。

输入格式

第一行，三个整数 $n,m,k\ (1≤n,m≤1000$，$1≤k≤10)$；

接下来 $n$ 行，每行包含 $m$ 个整数，表示颜色。其中 $0$ 表示未涂色，非 $0$ 表示颜色的编号，颜色编号为 $1$ 到 $k$。

输出格式

一行一个整数，表示涂色方案对 $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