B. Различные пути
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Дана прямоугольная доска, состоящая из 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).

Примеры
Входные данные
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