4089: CF111 - D. Petya and Coloring
[Creator : ]
Description
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.
Input
The first line contains space-separated integers $n,m,k\ (1≤n,m≤1000,\ 1≤k≤10^6)$ − the board's vertical and horizontal sizes and the number of colors respectively.
Output
Print the answer to the problem. As the answer can be quite a large number, you should print it modulo $10^9+7$.
Sample 1 Input
2 2 1
Sample 1 Output
1
Sample 2 Input
2 2 2
Sample 2 Output
8
Sample 3 Input
3 2 2
Sample 3 Output
40