Petya and Coloring

题意翻译

题目描述 -- $Petya$喜欢计数。他想计算: 用$K$种颜色绘制尺寸为$n*m$ ( $n$行,$m$列)的矩形棋盘的方法数。 此外,着色应满足以下要求: 对于沿格子的线穿过的任何垂直线,会将棋盘分成两个非空的部分,这两个部分中的不同颜色的数量应相同。 帮助$Petya$对这些颜色进行计数。 输入格式 --- 第一行有三个用空格隔开的整数$n$,$m$,$k$ $(1<=n,m<=1000,1<=k<=1e6)$ 含义如题。 输入共一行。 输出格式 -- 输出如题要求的答案。由于答案可能过大,输出其模$1e9+7$的值。

题目描述

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 $ ).

输入输出样例

输入样例 #1

2 2 1

输出样例 #1

1

输入样例 #2

2 2 2

输出样例 #2

8

输入样例 #3

3 2 2

输出样例 #3

40