Маленький Петя любит считать. Он хочет посчитать, сколько существует способов раскрасить прямоугольную клетчатую доску размера n × m (n строк, m столбцов) в k цветов. При этом раскраска должна обладать следующим свойством: для любой вертикальной прямой, проходящей по линиям сетки и делящей доску на две непустые части, количество различных цветов в обеих этих частях должно быть одинаковым. Помогите Пете посчитать количество таких раскрасок.
Выходные данные
Выведите ответ на задачу. Так как ответ может быть достаточно большим, нужно вывести его по модулю 109 + 7 (1000000007).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2 1
|
1
|
|
2
|
2 2 2
|
8
|
|
3
|
3 2 2
|
40
|