D. Петя и раскраски
ограничение по времени на тест
5 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Маленький Петя любит считать. Он хочет посчитать, сколько существует способов раскрасить прямоугольную клетчатую доску размера n × m (n строк, m столбцов) в k цветов. При этом раскраска должна обладать следующим свойством: для любой вертикальной прямой, проходящей по линиям сетки и делящей доску на две непустые части, количество различных цветов в обеих этих частях должно быть одинаковым. Помогите Пете посчитать количество таких раскрасок.

Входные данные

В первой строке через пробел записаны целые числа n, m и k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 106) — размерность доски по вертикали, размерность доски по горизонтали и количество цветов соответственно.

Выходные данные

Выведите ответ на задачу. Так как ответ может быть достаточно большим, нужно вывести его по модулю 109 + 7 (1000000007).

Примеры
Входные данные
2 2 1
Выходные данные
1
Входные данные
2 2 2
Выходные данные
8
Входные данные
3 2 2
Выходные данные
40