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<sup class="upper-index">6</sup>) — the board's vertical and horizontal sizes and the number of colors respectively.
2 2 1
1
2 2 2
8
3 2 2
40
7 8 15
422409918
5 3 1
1
5 100 1
1
5 20 25
375284458
6 6 8
522449402
1 1 1000000
1000000
3 3 2
290
1000 1000 1000000
396597934
1000 2 1000000
356256162
1000 1 992929
466214417
997 752 10001
353027886
994 2 999999
273778994
1 1000 298298
298298
2 1000 100202
648728052
3 997 999997
291903372
777 777 777777
874869916
105 3 2
207720058
105 3 3
481254277
126 125 440715
387326012
755 51 70160
188325679
385 978 699604
207434967
663 904 329049
599285820
293 183 442142
427008206
922 109 71587
433271191
552 36 701031
203545141
182 314 814124
753768028
812 240 443569
570986336
595 881 798832
551206173
694 685 739154
621135202
793 840 679477
737614679
892 996 619800
499746149
990 800 43771
959043509
89 955 984094
559468061
188 759 924417
709624881
287 915 864740
945465938
738 718 805063
428428914
837 874 229034
359437873
991 301 743241
583160905
import math
MOD = 1000000007
fact = [0 for i in range(10 ** 6 + 1)]
rfact = [0 for i in range(10 ** 6 + 1)]
n,m,k = map(int,input().split())
if m==1:
    print(k**m%MOD)
    exit()
def Comb(n,k): #Hallar las combinaciones de n en k
    comb= math.factorial(n)/(math.factorial(k)*math.factorial(n-k))
    return int(comb)%MOD

def ColorearCeldas(c): #Cantidad de formas de rellenar n celdas con exactamente c colores
    resp = c**n #Toda las posibles formas de distribuir  c colores en n celdas
    for i in range(1,c):
        resp-= Comb(c,i)*ColorearCeldas(i) #Le restamos la cantidad de formas en que coloreamos con menos de c colores, multiplicado por la cantidad de formas en que podemos escoger los i colores
    return resp%MOD

fact[0] = 1
rfact[0] = 1
for i in range(1, k + 1):
    fact[i] = (fact[i - 1] * i) % MOD
    rfact[i] = (rfact[i - 1] * pow(i, MOD - 2, MOD)) % MOD

ans=0
for y in range(n):     #Iteramos por todos los posibles colores usados para colorear el tablero entero
    for x in range(y,n+1): #Iterar por todos los posibles colores unicos en la primera columna y consecuentemente los posibles colores de la ultoma columna
        if 2*x-y<=k:
            resp= Comb(k,2*x-y)%MOD                  #Colores comunes
            resp*=Comb(2*x-y,x-y)%MOD                #Escogemos los colores utilizados
            resp*=Comb(x,x-y)%MOD               #Formas de escoger del conjunto total los colores únicos para la columna 1           #Formas de elegir del resto los colores únicos para la última columna
            resp*=ColorearCeldas(x)**2%MOD  #Formas de organizar los colores elegidos en la primera y ultima columna
            resp*=fact[x]%MOD
            resp*=fact[x]%MOD #Formas de organizar los colores elegidos en las columnas del medio
            resp*=y**(n*(m-2))%MOD
            ans+=resp
            ans=ans%MOD

print(resp%MOD)
