Problem3860--Petya and Coloring

3860: Petya and Coloring

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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≤106) − 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 109+7 (1000000007).

Examples
Input
2 2 1
Output
1
Input
2 2 2
Output
8
Input
3 2 2
Output
40

Source/Category