Дана прямоугольная доска, состоящая из n × m клеток. Некоторые из клеток уже покрашены в какой-то из k цветов. Требуется покрасить каждую непокрашенную клетку в один из k цветов таким образом, чтобы любой путь из верхней левой клетки в правую нижнюю (переходы возможны только по клеткам соседним по стороне и только вниз или вправо) не содержал в себе двух клеток одинакового цвета.
Выведите остаток от деления количества возможных раскрасок на 1000000007 (109 + 7).
Выходные данные
Выведите остаток от деления количества возможных раскрасок на 1000000007 (109 + 7).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2 4
0 0
0 0
|
48
|
|
2
|
2 2 4
1 2
2 1
|
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
|
3628800
|
|
4
|
2 6 10
1 2 3 4 5 6
0 0 0 0 0 0
|
4096
|