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
def inv(x):
    return pow(x, mod - 2, mod)
def C(n, k):
    if (k > n):
        return 0
    return f[n] * inv(f[k]) % mod * inv(f[n - k]) % mod
def calc(x, y):
    if not y:
        return pow(x, n, mod) - pow(x - 1, n, mod)
    return (pow(x, n, mod) * C(k, y) - pow(x - 1, n, mod) * C(k, y - 1)) % mod
n, m, k = map(int, input().split())
mod = 1000000007
f = [1]
for i in range(1, 1000001):
    f.append(f[-1] * i % mod)
ans = 0
if m == 1:
    print(pow(k, n, mod))
    exit()
for x in range(1, min(k, n) + 1):
    if m == 2:
        ans += calc(x, x) * calc(x, x)
        ans %= mod
    else:
        for y in range(0, x + 1):
            ans += calc(x, x) * calc(x, x - y) % mod * pow(y, n * (m - 2), mod)
            ans %= mod
print(ans)
