CF111D 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

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