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
from typing import List, Set, Dict, Tuple, Text, Optional, Callable, Any
from collections import deque
import collections
from types import GeneratorType
import itertools
import operator
import functools
import random
import copy
import heapq
import math
import sys
import os
from atexit import register
from io import BytesIO, IOBase
import __pypy__  # type: ignore

EPS = 10**-12

################
# INPUT OUTPUT #
################

# From: https://github.com/cheran-senthil/PyRival/blob/master/templates/template_py3.py

BUFSIZE = 8192


class FastIO(IOBase):
  newlines = 0

  def __init__(self, file):
    self._fd = file.fileno()
    self.buffer = BytesIO()
    self.writable = "x" in file.mode or "r" not in file.mode
    self.write = self.buffer.write if self.writable else None

  def read(self):
    while True:
      b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
      if not b:
        break
      ptr = self.buffer.tell()
      self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
    self.newlines = 0
    return self.buffer.read()

  def readline(self):
    while self.newlines == 0:
      b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
      self.newlines = b.count(b"\n") + (not b)
      ptr = self.buffer.tell()
      self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
    self.newlines -= 1
    return self.buffer.readline()

  def flush(self):
    if self.writable:
      os.write(self._fd, self.buffer.getvalue())
      self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
  def __init__(self, file):
    self.buffer = FastIO(file)
    self.flush = self.buffer.flush
    self.writable = self.buffer.writable
    self.write = lambda s: self.buffer.write(s.encode("ascii"))
    self.read = lambda: self.buffer.read().decode("ascii")
    self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


class Input(object):
  def rawInput(self):
    return sys.stdin.readline().rstrip("\r\n")

  def readInt(self):
    return int(self.rawInput())


class Output(object):
  def __init__(self):
    self.out = __pypy__.builders.StringBuilder()

  def write(self, text):
    # type: (str) -> None
    self.out.append(str(text))

  def writeLine(self, text):
    # type: (str) -> None
    self.write(str(text) + '\n')

  def finalize(self):
    sys.stdout.write(self.out.build())
    sys.stdout.flush()


###########
# LIBRARY #
###########


def bootstrap(f, stack=[]):
  # Deep Recursion helper.
  # From: https://github.com/cheran-senthil/PyRival/blob/c1972da95d102d95b9fea7c5c8e0474d61a54378/docs/bootstrap.rst
  # Usage:

  # @bootstrap
  # def recur(n):
  #   if n == 0:
  #     yield 1
  #   yield (yield recur(n-1)) * n
  def wrappedfunc(*args, **kwargs):
    if stack:
      return f(*args, **kwargs)
    else:
      to = f(*args, **kwargs)
      while True:
        if type(to) is GeneratorType:
          stack.append(to)
          to = next(to)
        else:
          stack.pop()
          if not stack:
            break
          to = stack[-1].send(to)
      return to

  return wrappedfunc


int_add = __pypy__.intop.int_add
int_sub = __pypy__.intop.int_sub
int_mul = __pypy__.intop.int_mul


def make_mod_mul(mod):
  fmod_inv = 1.0 / mod

  def mod_mul(a, b, c=0):
    res = int_sub(int_add(int_mul(a, b), c), int_mul(
        mod, int(fmod_inv * a * b + fmod_inv * c)))
    if res >= mod:
      return res - mod
    elif res < 0:
      return res + mod
    else:
      return res

  return mod_mul


def isPrime(number):
  # type: (int) -> bool
  # Return if number is prime.
  # Complexity: n^{0.5}
  '''
  >>> list(map(isPrime, [0, 1, 2, 4, 5, 8, 11, 21, 23]))
  [False, False, True, False, True, False, True, False, True]
  '''

  if number <= 1:
    return False
  if number == 2:
    return True
  if number % 2 == 0:
    return False
  for factor in range(3, int(math.sqrt(number))+1, 2):
    if number % factor == 0:
      return False

  return True


class Combination(object):
  '''
  >>> tp = Combination(10, 11)
  >>> tp.factorial(0)
  1
  >>> tp.factorial(1)
  1
  >>> tp.factorial(2)
  2
  >>> tp.factorial(3)
  6
  >>> tp.factorial(4)
  2
  >>> tp.factorial(10)
  10
  >>> tp.combination(0, 0)
  1
  >>> tp.combination(1, 1)
  1
  >>> tp.combination(10, 1)
  10
  >>> tp.combination(1, 10)
  0
  >>> tp.combination(1, 0)
  1
  >>> tp.combination(10, 0)
  1
  >>> tp.combination(4, 2)
  6
  >>> tp.combination(6, 2)
  4
  >>> tp.combination(10, 8)
  1
  >>> tp.combination(10, 10)
  1
  >>> tp.permutation(0, 0)
  1
  >>> tp.permutation(1, 1)
  1
  >>> tp.permutation(10, 1)
  10
  >>> tp.permutation(1, 10)
  0
  >>> tp.permutation(1, 0)
  1
  >>> tp.permutation(10, 0)
  1
  >>> tp.permutation(4, 2)
  1
  >>> tp.permutation(6, 2)
  8
  >>> tp.permutation(10, 8)
  5
  >>> tp.permutation(10, 10)
  10
  >>> tp = Combination(10, 10)
  >>> tp.factorial(0)
  1
  >>> tp.factorial(1)
  1
  >>> tp.factorial(2)
  2
  >>> tp.factorial(3)
  6
  >>> tp.factorial(4)
  4
  >>> tp.factorial(10)
  0
  >>> tp.combination(0, 0)
  1
  >>> tp.combination(1, 1)
  1
  >>> tp.combination(9, 1)
  9
  >>> tp.combination(10, 1)
  0
  >>> tp.combination(1, 10)
  0
  >>> tp.combination(1, 0)
  1
  >>> tp.combination(10, 0)
  1
  >>> tp.combination(4, 2)
  6
  >>> tp.combination(6, 2)
  5
  >>> tp.combination(10, 8)
  5
  >>> tp.permutation(0, 0)
  1
  >>> tp.permutation(1, 1)
  1
  >>> tp.permutation(10, 1)
  0
  >>> tp.permutation(1, 10)
  0
  >>> tp.permutation(1, 0)
  1
  >>> tp.permutation(10, 0)
  1
  >>> tp.permutation(4, 2)
  2
  >>> tp.permutation(6, 2)
  0
  >>> tp.permutation(10, 8)
  0
  >>> tp.permutation(10, 10)
  0
  '''

  def __init__(self, max_n, modulo):
    # type: (int, int) -> None
    self._max_n = max_n + 5
    if modulo > 2 * 10**9:
      self._mul = lambda a, b: (a*b) % modulo
    else:
      self._mul = make_mod_mul(modulo)
    self._modulo = modulo

    # precompute factorial
    self._factorial = [0] * self._max_n
    self._factorial[0] = 1
    for i in range(1, self._max_n):
      self._factorial[i] = self._mul(self._factorial[i-1], i)

    self._mod_prime = isPrime(modulo)

    if self._mod_prime:
      self._precomputePrimeMod()
    else:
      self._precomputeDp()

  def _precomputePrimeMod(self):
    # compute modular inverses
    n = self._max_n
    modulo = self._modulo

    mod_inverses = [0] * n
    mod_inverses[1] = 1
    for i in range(2, n):
      mod_inverses[i] = (modulo - self._mul(modulo // i,
                         mod_inverses[modulo % i])) % modulo

    factorial_inverses = [0] * n
    factorial_inverses[0] = factorial_inverses[1] = 1

    for i in range(2, n):
      factorial_inverses[i] = self._mul(
          factorial_inverses[i-1], mod_inverses[i])

    self._factorial_inverse = factorial_inverses

  def _precomputeDp(self):
    n = self._max_n  # type: int
    modulo = self._modulo

    # combination DP:
    self._dp_combination = [0] * (n*n)
    dp = self._dp_combination

    # take 0 from any a is 1
    for i in range(n):
      dp[i * n] = 1

    for i in range(1, n):
      for j in range(1, i+1):
        # take j from i
        dp[i * n + j] = (dp[(i-1) * n + j] + dp[(i-1) * n + j - 1]) % modulo

    # combination DP:
    self._dp_permutation = [0] * (n*n)
    dp = self._dp_permutation

    # take 0 from any a is 1
    for i in range(n):
      dp[i * n] = 1

    for i in range(1, n):
      for j in range(1, i+1):
        # take j from i
        dp[i * n + j] = self._mul(dp[(i-1) * n + j - 1], i)

  def combination(self, total, take):
    # type: (int, int) -> int
    assert 0 <= total < self._max_n
    assert 0 <= take < self._max_n
    if self._mod_prime:
      if take > total:
        return 0

      top = self._factorial[total]
      bottom1 = self._factorial_inverse[take]
      bottom2 = self._factorial_inverse[total - take]
      return self._mul(self._mul(top, bottom1), bottom2)
    else:
      return self._dp_combination[total * self._max_n + take]

  def permutation(self, total, take):
    # type: (int, int) -> int
    assert 0 <= total < self._max_n
    assert 0 <= take < self._max_n
    if self._mod_prime:
      if take > total:
        return 0

      top = self._factorial[total]
      bottom = self._factorial_inverse[total - take]
      return self._mul(top, bottom)
    else:
      return self._dp_permutation[total * self._max_n + take]

  def factorial(self, i):
    assert 0 <= i < self._max_n
    return self._factorial[i]


#########
# LOGIC #
#########


def solve(n: int, m: int, k: int):
  modulo = 10**9 + 7
  if m == 1:
    return pow(k, n, modulo)

  combin = Combination(1050, modulo)

  mul = make_mod_mul(modulo)

  memopow = [-1] * (3000)

  def mod_pow(x, y):
    if memopow[x] != -1:
      return memopow[x]

    if y == 0:
      return 1

    res = 1
    while y > 1:
      if y & 1 == 1:
        res = mul(res, x)
      x = mul(x, x)
      y >>= 1

    memopow[x] = mul(res, x)
    return memopow[x]

  memo = [-1] * (1050 * 1050)

  # cara color n degan colors colors
  @bootstrap
  def assignways(n, colors):
    if colors > n:
      yield 0
    if n == 0:
      yield 1
    if colors == 0:
      yield 0

    key = n * 1050 + colors
    if memo[key] != -1:
      yield memo[key]

    # two possibilities
    # pick a color and it'll get reused later
    # pick a color and it'll be used here for the last time
    reused = mul((yield assignways(n-1, colors)), colors)
    last = mul((yield assignways(n-1, colors-1)), colors)
    ans = (reused + last) % modulo
    memo[key] = ans
    yield ans

  res = 0
  for unique in range(n+1):
    for share in range(n+1):
      if unique * 2 + share <= k:
        # ways to pick unique and shares times ways to assign them

        # ways to pick:
        pick = mul(
            combin.combination(k, unique),
            combin.combination(k - unique, unique),
        )
        pick = mul(
            pick,
            combin.combination(k - unique - unique, share)
        )

        # ways to assign:
        ways = assignways(n, unique+share)

        # ways to fill the rest:
        rest = mod_pow(share, (n * (m-2)))

        res += mul(mul(mul(pick, ways), ways), rest)

  return res


def main(inp: Input, out: Output) -> Any:
  n, m, k = map(int, inp.rawInput().split())
  out.writeLine(solve(n, m, k))


###############
# BOILERPLATE #
###############

output_obj = Output()
main(Input(), output_obj)
output_obj.finalize()
