#include <string.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

constexpr int mod = 1000000007;

void mpl(int &x,int y) {
    x += y;
    if(x >= mod) x -= mod;
}

int dp[2020][2020];
int f[2020202],f2[2020][2020];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,k;
    cin >> n >> m >> k;
    f[0] = 1;
    for(int i = 1; i <= n; i++) {
        f[i] = 1ll*f[i-1]*k%mod;
    }
    for(int i = 0; i <= m; i++) {
        if(k-i < 0) break;
        f2[i][0] = 1;
        for(int j = 1; j <= m; j++) {
            f2[i][j] = 1ll*f2[i][j-1]*(k-i-j+1)%mod;
        }
    }
    dp[0][0] = 1;
    for(int i = 0; i <= m; i++) {
        for(int j = 0; j <= m; j++) {
            if(!dp[i][j]) continue;
            mpl(dp[i+1][j+1],1ll*dp[i][j]*(k-j)%mod);
            int a = j*2-i;
            mpl(dp[i+1][j],1ll*dp[i][j]*a%mod);
        }
    }
    int res = 0;
    for(int i = 0; i <= m; i++) {
        mpl(res,dp[m][i]);
    }
    int ans = 0;
    for(int i = 1; i <= m/2; i++) {
        int sum = 0;
        for(int j = 0; j <= m; j++) {
            mpl(sum,1ll*dp[m-2*i][j]*f2[j][i]%mod);
            mpl(res,mod-1ll*dp[m-2*i][j]*f2[j][i]%mod);
        }
        for(int j = 1; j <= n; j += 2) {
            if(m+(j-1)*(m-i) > n) break;
            int a = m+(j-1)*(m-i),b = m-i;
            int mi = min(b,n-a+1);
            mpl(ans,1ll*sum*mi%mod*f[n-a]%mod);
            if(n >= a+b) {
                mpl(ans,1ll*sum*(n-a-b+1)%mod*f[n-a-b]%mod*(f[b]+mod-1)%mod);
            }
        }
    }
    mpl(ans,1ll*res*(n-m+1)%mod*f[n-m]%mod);
    cout << ans << "\n";
}