#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define SZ(a) ((int)a.size())

const int MOD = 1e9 + 7;
const int MAXC = 4005;
const int MAXN = 2e6;

void add(int &x, int val) {
    x += val;
    if (x >= MOD) x -= MOD;
}

int pw(int a, int n) {
    int res = 1;
    for (; n; n >>= 1, a = (ll)a * a % MOD)
        if (n & 1)
            res = (ll)res * a % MOD;
    return res;
}

int rC[MAXC][MAXC], fac[MAXC], inv[MAXC], ipw2[MAXC];

int C(int n, int m) { // O(m)
    if (n < m) return 0;
    int res = 1;
    for (int i = 0; i < m; ++i) {
        res = (ll)res * (n - i) % MOD;
        res = (ll)res * inv[i + 1] % MOD;
    }
    return res;
}

int P(int n, int m) { // O(m)
    if (n < m) return 0;
    int res = 1;
    for (int i = 0; i < m; ++i) {
        res = (ll)res * (n - i) % MOD;
    }
    return res;
}

int S[MAXC], L[MAXC][MAXC], len[MAXN];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    fac[0] = 1;
    for (int i = 1; i < MAXC; ++i)
        fac[i] = (ll)fac[i - 1] * i % MOD;
    inv[1] = 1;
    for (int i = 2; i < MAXC; ++i)
        inv[i] = (ll)(MOD - MOD / i) * inv[MOD % i] % MOD;
    ipw2[0] = 1;
    for (int i = 1; i < MAXC; ++i)
        ipw2[i] = (ll)ipw2[i - 1] * inv[2] % MOD;
    int n, m, k, ans = 0;
    cin >> n >> m >> k;

    for (int i = 0; i <= m; ++i) {
        rC[i][0] = 1;
        for (int j = 1; j <= m && j <= (k - i); ++j)
            rC[i][j] = (ll)rC[i][j - 1] * (k - i - (j - 1)) % MOD * inv[j] % MOD; 
    }

    auto get_C = [&](int p, int q) {
        if (p < q) return 0;
        return rC[k - p][q];  
    };

    /*for (int d = 0; d <= m / 2; ++d) { // need optimized
        for (int x = 0; x <= m; ++x) {
            for (int i = 0; i <= x / 2; ++i)
                add(L[d][x], (ll)get_C(k - d, i) * get_C(k - i - d, x - 2 * i) % MOD * fac[x] % MOD * ipw2[i] % MOD);
            //cerr << "L " << d << " " << x << " = " << L[d][x] << "\n";
        }
    }*/

    auto get_L = [&](int d, int x) {
        int res = 0;   
        for (int i = 0; i <= x / 2; ++i)
            add(res, (ll)get_C(k - d, i) * get_C(k - i - d, x - 2 * i) % MOD * fac[x] % MOD * ipw2[i] % MOD);
        return res;
    };

    for (int x = 1; x <= m / 2; ++x) {
        S[x] = (ll)P(k, x) * get_L(x, m - 2 * x) % MOD;
        //cerr << "S " << x << " = " << S[x] << "\n";
    }
    for (int x = 1; x <= n; ++x) {
        len[x] = (ll)(n - x + 1) * pw(k, n - x) % MOD;
        //cerr << "len " << x << " = " << len[x] << "\n";
    }

    // case 1
    for (int x = 1; x <= m / 2; ++x) { 
        int sum = 0;
        for (int j = 1; (x + (m - x) * j) <= n; ++j)
            if (j & 1)
                add(sum, len[x + (m - x) * j]);
            else
                add(sum, MOD - len[x + (m - x) * j]);
        add(ans, (ll)S[x] * sum % MOD);
    }
    //cerr << "after case1: " << ans << "\n";

    // case 2
    int sum = get_L(0, m);
    for (int x = 1; x <= m / 2; ++x)
        add(sum, MOD - S[x]);
    add(ans, (ll)len[m] * sum % MOD);

    cout << ans << "\n";
}