#include <bits/stdc++.h>
using namespace std;

const int MXM = 2005;
const int DVS = 1e9 + 7;
const int MXN = 1000005;
int N, M, K, cnt[MXM][MXM], kprd[MXM][MXM], kpow[MXN], scnt[MXM], ans;

int main() {
  cin >> N >> M >> K;
  cnt[0][0] = 1;
  for (int i(1); i <= M; ++i) {
    for (int j(max(0, i - K)); j + j <= i; ++j) {
      cnt[i][j] = (cnt[i - 1][j] * 1LL * (K - i + 1 + j) +
                   (j ? cnt[i - 1][j - 1] * 1LL * (i + 1 - j - j) : 0LL)) % DVS;
    }
  }
  for (int l(0); l <= M && l <= K; ++l) {
    kprd[l][l] = K - l;
    for (int r(l + 1); r <= M && r <= K; ++r)
      kprd[l][r] = kprd[l][r - 1] * 1LL * (K - r) % DVS;
  }
  for (int i(kpow[0] = 1); i <= N; ++i) kpow[i] = kpow[i - 1] * 1LL * K % DVS;
  for (int i(max(0, M - K)); i + i <= M; ++i)
    scnt[0] = (scnt[0] + cnt[M][i]) % DVS;
  for (int i(1); i + i <= M; ++i) {
    for (int j(0); i + i + j <= M; ++j) {
      int v(M - i - i - j);
      scnt[i] = (scnt[i] + cnt[M - i - i][j] * 1LL * kprd[v][v + i - 1]) % DVS;
    }
    scnt[0] = (scnt[0] + DVS - scnt[i]) % DVS;
    int ths(0);
    for (int j(1), len(M); len <= N; ++j, len += M - i) {
      ths = (ths + (j & 1 ? 1 : DVS - 1) * 1LL *
                   (N - len + 1) % DVS * kpow[N - len]) % DVS;
    }
    ans = (ans + ths * 1LL * scnt[i]) % DVS;
  }
  ans = (ans + (N - M + 1) % DVS * 1LL * kpow[N - M] % DVS * scnt[0]) % DVS;
  cout << ans << endl;
  return 0;
}