A8189. Petya and Coloring

Little Petya loves counting. He wants to count the number of ways to paint a rectangular checkered board of size $n×m$ ( $n$ rows, $m$ columns) in $k$ colors. Besides, the coloring should have the following property: for any vertical line that passes along the grid lines and divides the board in two non-empty parts the number of distinct colors in both these parts should be the same. Help Petya to count these colorings.

The first line contains space-separated integers $n$ , $m$ and $k$ ( $1<=n,m<=1000,1<=k<=10^{6}$ ) — the board's vertical and horizontal sizes and the number of colors respectively.

Print the answer to the problem. As the answer can be quite a large number, you should print it modulo $10^{9}+7$ ( $1000000007$ ).