CF111D Petya and Coloring

-- $Petya$喜欢计数。他想计算： 用$K$种颜色绘制尺寸为$n*m$ ( $n$行，$m$列)的矩形棋盘的方法数。 此外，着色应满足以下要求： 对于沿格子的线穿过的任何垂直线，会将棋盘分成两个非空的部分，这两个部分中的不同颜色的数量应相同。 帮助$Petya$对这些颜色进行计数。

--- 第一行有三个用空格隔开的整数$n$，$m$，$k$ $(1

-- 输出如题要求的答案。由于答案可能过大，输出其模$1e9+7$的值。