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*$ and $*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$ ($1000000007$).