#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
template <unsigned umod>
struct modint {/*{{{*/
  static constexpr int mod = umod;
  unsigned v;
  modint() = default;
  template <class T, enable_if_t<is_integral<T>::value>* = nullptr> modint(const T& _y) :
    v((unsigned)(_y % mod + (is_signed<T>() && _y < 0 ? mod : 0))) {}
  modint& operator+=(const modint& rhs) { v += rhs.v; if (v >= umod) v -= umod; return *this; }
  modint& operator-=(const modint& rhs) { v -= rhs.v; if (v >= umod) v += umod; return *this; }
  modint& operator*=(const modint& rhs) { v = (unsigned)(1ull * v * rhs.v % umod); return *this; }
  modint& operator/=(const modint& rhs) { assert(rhs.v); return *this *= qpow(rhs, mod - 2); }
  friend int raw(const modint& self) { return self.v; }
  friend ostream& operator<<(ostream& os, const modint& self) { return os << raw(self); }
  friend modint operator+(modint lhs, const modint& rhs) { return lhs += rhs; }
  friend modint operator-(modint lhs, const modint& rhs) { return lhs -= rhs; }
  friend modint operator*(modint lhs, const modint& rhs) { return lhs *= rhs; }
  friend modint operator/(modint lhs, const modint& rhs) { return lhs /= rhs; }
  friend modint qpow(modint a, int b) {
    assert(b >= 0);
    modint r = 1;
    while (b) {
      if (b & 1) r *= a;
      if (b >>= 1) a *= a;
    }
    return r;
  }
};/*}}}*/
using mint = modint<int(1e9 + 7)>;
template <int N>
struct C_prime {
  mint fac[N + 10], ifac[N + 10];
  C_prime() {
    fac[0] = 1;
    for (int i = 1; i <= N; i++) fac[i] = fac[i - 1] * i;
    ifac[N] = 1 / fac[N];
    for (int i = N; i >= 1; i--) ifac[i - 1] = ifac[i] * i;
  }
  mint operator()(int n, int m) const { return n >= m ? fac[n] * ifac[m] * ifac[n - m] : 0; }
  mint inv(int x) const { return ifac[x] * fac[x - 1]; }
};
C_prime<2000010> binom;
struct underpow {
  vector<mint> kd, ikd;
  underpow() = default;
  underpow(int m, int k) : kd(m + 1), ikd(m + 1) {
    // kd[i] = k^\underline i
    kd[0] = 1;
    for (int i = 1; i <= m; i++) kd[i] = kd[i - 1] * (k - i + 1);
    ikd[m] = 1 / kd[m];
    for (int i = m; i >= 1; i--) ikd[i - 1] = ikd[i] * (k - i + 1);
  }
};
int n, m, K;
mint qpK[1000010], iqp2[4010];
void init() {
  qpK[0] = 1;
  for (int i = 1; i <= n; i++) qpK[i] = qpK[i - 1] * K;
  mint iz = binom.inv(2);
  iqp2[0] = 1;
  for (int i = 1; i <= 4000; i++) iqp2[i] = iqp2[i - 1] * iz;
}
mint calc(int m, int k) {
  underpow udp(min(m, k), k);
  mint res = 0;
  for (int i = max(m - k, 0); i <= min(k, m / 2); i++) {
    res += udp.kd[i] * binom.ifac[i] * iqp2[i] * udp.kd[m - i] * udp.ikd[i] * binom.ifac[m - 2 * i];
//  debug("i = %d, res += %d * %d * %d\n", i, raw(udp.kd[i] * binom.ifac[i]), raw(iqp2[i]), raw(udp.kd[m - i] * udp.ikd[i] * binom.ifac[m - 2 * i]));
  }
  debug("calc(%d, %d) = %d\n", m, k, raw(res * binom.fac[m]));
  return res * binom.fac[m];
}
mint coeS(int m) { return (n - m + 1) * qpK[n - m]; }
int main() {
#ifndef LOCAL
#ifdef NF
  freopen("lake.in", "r", stdin);
  freopen("lake.out", "w", stdout);
#endif
  cin.tie(nullptr)->sync_with_stdio(false);
#endif
  cin >> n >> m >> K;
  init();
  mint ans = calc(m, K) * coeS(m);
  debug("ans0 = %d\n", raw(ans));
  underpow udp(min(m, K), K);
  for (int i = 1; i <= min(K, m / 2); i++) {
    mint coeP = udp.kd[i] * calc(m - 2 * i, K - i);
    for (int j = 2; i + j * (m - i) <= n; j++) {
      ans += (j & 1 ? +1 : -1) * coeP * coeS(i + j * (m - i));
    }
  }
  cout << ans << endl;
  return 0;
}