/**
 * @file qoj8211-1.cpp
 * @author n685
 * @brief
 * @date 2024-02-19
 *
 *
 */
#include <bits/stdc++.h>

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
#endif

template <class T> constexpr std::pair<T, T> exEucl(T a, T b) {
  if (a < b) {
    // auto [x, y] = exEucl(b, a);
    T x, y;
    std::tie(x, y) = exEucl(b, a);
    return {y, x};
  }
  if (b == 0) {
    assert(a == 1);
    return {1, 0};
  }
  // auto [x, y] = exEucl(b, a % b);
  T x, y;
  std::tie(x, y) = exEucl(b, a % b);
  return {y, x - (a / b) * y};
}
template <
    class T, class U,
    typename std::enable_if<std::is_integral<U>::value, bool>::type = true>
constexpr T binpow(T a, U b) {
  // 0^0 = 1
  T res = 1;
  while (b > 0) {
    if (b % 2 == 1) {
      res *= a;
    }
    a *= a;
    b /= 2;
  }
  return res;
}

template <class Md, class V = int64_t> struct Mod {
  using T = typename std::decay<decltype(Md::value)>::type;
  T val = 0;

  template <class U> static constexpr T normalize(U val) {
    if (val <= -Md::value || Md::value <= val) {
      val %= Md::value;
    }
    if (val < 0) {
      val += Md::value;
    }
    return static_cast<T>(val);
  }

  constexpr Mod() : val(0) {}
  template <class U, typename std::enable_if<std::is_integral<U>::value,
                                             bool>::type = true>
  constexpr Mod(U _val) {
    val = normalize(_val);
  }

  // addition
  constexpr Mod &operator+=(Mod b) {
    val += b.val;
    if (val >= Md::value) {
      val -= Md::value;
    }
    return *this;
  }
  friend constexpr Mod operator+(Mod a, Mod b) { return (a += b); }
  constexpr Mod &operator++() { return (*this += 1); }
  constexpr Mod operator++(int) {
    Mod res = *this;
    ++(*this);
    return res;
  }

  // subtraction
  constexpr Mod &operator-=(Mod b) {
    val -= b.val;
    if (val < 0) {
      val += Md::value;
    }
    return *this;
  }
  friend constexpr Mod operator-(Mod a, Mod b) { return (a -= b); }
  constexpr Mod &operator--() { return (*this -= 1); }
  constexpr Mod operator--(int) {
    Mod res = *this;
    --(*this);
    return res;
  }

  // multiplication
  constexpr Mod &operator*=(Mod b) {
    val = static_cast<T>(static_cast<V>(val) * b.val % Md::value);
    return *this;
  }
  friend constexpr Mod operator*(Mod a, Mod b) { return (a *= b); }

  template <class U> constexpr Mod binpow(U b) const {
    return ::binpow(*this, b);
  }
  constexpr Mod inv() const {
    return Mod(exEucl(static_cast<V>(val), static_cast<V>(Md::value)).first);
    // return binpow(Md::value - 2);
  }

  // comparison
  constexpr bool operator==(Mod b) const { return (val == b.val); }
  // constexpr auto operator<=>(const Mod &b) const = default;
  constexpr bool operator!=(Mod b) const { return (val != b.val); }
  constexpr bool operator<(Mod b) const { return (val < b.val); }
  constexpr bool operator>(Mod b) const { return (val > b.val); }
  constexpr bool operator<=(Mod b) const { return (val <= b.val); }
  constexpr bool operator>=(Mod b) const { return (val >= b.val); }

  // io
  friend std::istream &operator>>(std::istream &in, Mod &a) {
    V v;
    in >> v;
    a = Mod(v);
    return in;
  }
  friend std::ostream &operator<<(std::ostream &out, const Mod &a) {
    out << a.val;
    return out;
  }

  // conversion
  explicit constexpr operator T() const { return val; }
  constexpr const T &operator()() const { return val; }
  constexpr Mod operator-() const { return Mod(-val); }
};

constexpr int MOD = (int)1e9 + 7;
using Mint = Mod<std::integral_constant<std::decay<decltype(MOD)>::type, MOD>>;

std::vector<Mint> fac, ifac;
void init(int n) {
  fac.assign(n + 1, 0);
  ifac.assign(n + 1, 0);
  fac[0] = 1;
  for (int i = 1; i <= n; ++i) {
    fac[i] = fac[i - 1] * i;
  }
  ifac.back() = fac.back().inv();
  for (int i = n - 1; i >= 0; --i) {
    ifac[i] = ifac[i + 1] * (i + 1);
  }
}
Mint C(int n, int k) {
  if (n < k || n < 0 || k < 0) {
    return 0;
  }
  return fac[n] * ifac[n - k] * ifac[k];
}
Mint P(int n, int k) {
  if (n < k || n < 0 || k < 0) {
    return 0;
  }
  return fac[n] * ifac[n - k];
}

int main() {
#ifndef LOCAL
  std::cin.tie(nullptr)->sync_with_stdio(false);
#endif

  int n, m;
  int64_t k;
  std::cin >> n >> m >> k;
  init(n);

  std::vector<Mint> pk(n + 1);
  pk[0] = 1;
  for (int i = 1; i <= n; ++i) {
    pk[i] = pk[i - 1] * k;
  }
  std::vector<Mint> kp(n + 1);
  kp[0] = 1;
  for (int i = 1; i <= n; ++i) {
    kp[i] = kp[i - 1] * (k - i + 1);
  }
  auto ck = [&](int b) -> Mint {
    if (b < 0 || k < b) {
      return 0;
    }
    return kp[b] * ifac[b];
  };

  std::vector<std::vector<Mint>> dp(
      m + 1, std::vector<Mint>(std::min<int64_t>(m, k) + 1));
  dp[0][0] = 1;
  for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= (int)std::min<int64_t>(i, k); ++j) {
      dp[i][j] = dp[i - 1][j - 1] * i;
      if (i > 1) {
        dp[i][j] += dp[i - 2][j - 1] * C(i, 2);
      }
    }
    dp[i].resize(m + 1);
  }

  std::vector<Mint> num(m / 2 + 1);
  for (int i = 1; i <= m / 2; ++i) {
    int j = m - 2 * i;
    Mint prod = 1;
    for (int l = 0; l < i; ++l) {
      prod *= k - l;
    }
    for (int d = 0; d <= j; ++d) {
      num[i] += prod * dp[j][d] * ck(d);
      if (d < j) {
        prod *= Mint(k - d).inv() * (k - d - i);
      }
    }
  }
  Mint ans = 0;
  {
    Mint sum = 0;
    for (int j = 1; j <= m; ++j) {
      sum += dp[m][j] * ck(j);
    }
    for (int j = 1; j <= m / 2; ++j) {
      sum -= num[j];
    }
    ans += sum * (n - m + 1) * pk[n - m];
  }

  for (int i = 1; i <= m / 2; ++i) {
    int j = m - 2 * i;
    for (int sz = m, mul = 1; sz <= n; sz += i + j, mul *= -1) {
      ans += num[i] * mul * (n - sz + 1) * pk[n - sz];
    }
  }
  std::cout << ans << '\n';
}