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

using ll = long long;
using db = double;

const int mod = 1e9 + 7;
int add(int x, int y) {
    x += y;
    return x >= mod ? x - mod : x;
}
void addto(int& x, int y) {
    x += y;
    if (x >= mod) x -= mod;
}
int mul(int x, int y) {
    return 1ll * x * y % mod;
}

int qpow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = mul(ans, a);
        a = mul(a, a);
        b >>= 1;
    }
    return ans;
}

const int maxn = 1e6 + 10, maxm = 2e3 + 10;
int n, m, k;
int beautiful[maxm][maxm];
int wxw[maxm];
int mem[maxm][maxm];
int calc(int d, int w) {
    if (mem[d][w] != -1) return mem[d][w];
    int& ans = mem[d][w];
    if (k - d <= 0) return ans = 0;
    if (w == 0) return ans = 1;
    assert((k - d - w + 1 + mod) % mod >= 0);
    return ans = mul(calc(d, w - 1), (k - d - w + 1 + mod) % mod);
}
void solve() {
    memset(mem, -1, sizeof mem);
    cin >> n >> m >> k;
    beautiful[0][0] = 1;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            if (k - j + 1 > 0)
                addto(beautiful[i][j], mul(beautiful[i - 1][j - 1], k - j + 1));
            if (j * 2 - (i - 1) > 0)
                addto(beautiful[i][j], mul(beautiful[i - 1][j], j * 2 - (i - 1)));
            // cerr << beautiful[i][j] << " \n"[j == m];
        }
    }

    int ans = 0;
    for (int i = 1; i <= m; i++) {
        addto(wxw[0], beautiful[m][i]);
    }
    for (int w = 1; w * 2 <= m; w++) {
        int x = m - w * 2;
        for (int d = 0; d <= x; d++) {
            addto(wxw[w], mul(beautiful[x][d], calc(d, w)));
        }
        addto(wxw[0], mod - wxw[w]);
        for (int t = 1; t * x + (t + 1) * w <= n; t++) {
            int len = t * x + (t + 1) * w;
            addto(ans, mul(wxw[w], mul(n - len + 1, mul(qpow(k, n - len), t % 2 ? 1 : mod - 1))));
        }
    }
    addto(ans, mul(mul(n - m + 1, wxw[0]), qpow(k, n - m)));
    // for (int i = 0; i <= m; i++) {
    //     cout << wxw[i] << " \n"[i == m];
    // }
    cout << ans << "\n";
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}
/*

1-2-3-4-5
*/

/*
 5
 3 4 1
 2 1 1
 4 5 1
 3 2 1
 3
 2 2
 3 2
 1 2
*/