#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;

const int mod=1e9+7;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}

namespace polynomial{

    int INF=1e9;

    struct polyn{

        vector<int>a;

        polyn(){}
        polyn(vector<int>b){a=b;}

        void push_back(int x){
            a.pb(x);
        }
        int size(){return a.size();}
        void resize(int n){a.resize(n);}

        int& operator [](int x){
            if(x>=a.size())a.resize(x+1);
            return a[x];
        }

        polyn operator -(polyn b){
            polyn ret;
            ret.resize(max(b.size(),(int)a.size()));
            for(int i=0;i<a.size();i++)ret[i]=add(ret[i],a[i]);
            for(int i=0;i<b.size();i++)ret[i]=sub(ret[i],b[i]);
            return ret;
        }

        polyn operator +(polyn b){
            polyn ret;
            ret.resize(max(b.size(),(int)a.size()));
            for(int i=0;i<a.size();i++)ret[i]=add(ret[i],a[i]);
            for(int i=0;i<b.size();i++)ret[i]=add(ret[i],b[i]);
            return ret;
        }

        polyn operator *(int c){
            polyn ret=(*this);
            for(int i=0;i<ret.size();i++)ret[i]=mul(ret[i],c);
            return ret;
        }

        friend polyn operator *(const int c,polyn p){
            return p*c;
        }

        polyn brute_pmul(polyn b){
            polyn ret;
            ret.resize(a.size()+b.size()-1);
            for(int i=0;i<a.size();i++)
                for(int j=0;j<b.size();j++)
                    ret[i+j]=add(ret[i+j],mul(a[i],b[j]));
            return ret;
        }

        polyn operator *(polyn b){
            return brute_pmul(b);
        }

        polyn mod_xk(int n){
            polyn ret(a);
            ret.resize(n);
            return ret;
        }

        polyn neg(){
            polyn ret=(*this);
            for(int i=1;i<ret.size();i+=2)ret[i]=sub(0,ret[i]);
            return ret;
        }


        void ispis(){
            for(int i=0;i<a.size();i++)printf("%d ",a[i]);
            printf("POLYN ispis\n");
        }

    };

}

using namespace polynomial;

const int maxn=3e5+10;

int k;
polyn get_Px(int p,int c,int d,int r){

    int f0=step(k,p);
    int f1=sub(step(k,p+r),f0);

    polyn ret;
    ret[2]=sub(d,mul(c,f1));
    ret[1]=sub(f1,mul(c,f0));
    ret[0]=f0;

    return ret;
}
polyn get_Qx(int c){

    polyn ret,p1,p2;
    p1[0]=1;
    p1[1]=sub(0,1);

    p2[0]=1;
    p2[1]=1;

    p2=p1*p2;

    p1[1]=sub(0,c);
    ret=p1*p2;

    return ret;
}
polyn section(polyn p,int par){

    polyn ret;

    int curr=0;
    for(int i=par;i<p.size();i+=2)
        ret[curr++]=p[i];

    return ret;
}
int f_ex(int p,int i,int r){

    if(i<0)return 0;

    int c=step(k,r);
    int d=sub( step(k,p+2*r) , step(k,p+r));

    polyn P=get_Px(p,c,d,r);
    polyn Q=get_Qx(c);


    /// i-th term
    while(i){

        polyn gore=section(P*Q.neg(),i%2);
        polyn dole=section(Q*Q.neg(),0);

        P=gore;
        Q=dole;
        i/=2;
    }

    return mul(P[0],invv(Q[0]));
}
int f_ex_k(int p,int i,int r){

    if(i<0)return 0;

    int c=step(k,r);
    int d=sub( step(k,p+2*r) , step(k,p+r));

    polyn P=get_Px(p,c,d,r);
    polyn Q=get_Qx(c);
    polyn ppp;
    ppp[0]=1;
    ppp[1]=sub(0,c);
    Q=Q*ppp;


    /// i-th term
    while(i){

        polyn gore=section(P*Q.neg(),i%2);
        polyn dole=section(Q*Q.neg(),0);

        P=gore;
        Q=dole;
        i/=2;
    }

    return mul(P[0],invv(Q[0]));
}
int fksum(int n,int r){/// gets the sum k^n-i * f(i)

    if(n<0)return 0;

    int d=n/r;
    int d2=n%r;

    int ret=mul(f_ex_k(0,d-1,r),step(k,n-(d-1)*r));
    ret=mul(ret,r);

    int pom=mul(f_ex(0,d,r),step(k,n-d*r));
    ret=add(ret,mul(pom,add(d2,1)));

    return ret;
}

const int maxm=2010;
int dp[maxm][maxm],fact[maxm],inv[maxm],n,m;

int count_beautiful(int m,int k){

    if(m<0)return 0;

    int up=1;
    int ret=dp[m][0];
    for(int i=1;i<=m;i++){

        up=mul(up,k);
        k--;

        ret=add(ret,mul(dp[m][i],mul(mul(up,inv[i]),fact[i]) ) );
    }

    return ret;
}

int calc_singles(){
    return mul(mul(step(k,n-m),n-m+1),count_beautiful(m,k));
}

int main(){

    ///freopen("test.txt","r",stdin);

    scanf("%d %d %d",&n,&m,&k);

    dp[0][0]=1;
    for(int i=0;i<maxm;i++)
    for(int j=0;j<maxm;j++){
        if(i==0 && j==0)continue;

        if(i-1>=0){
            if(2*j-(i-1)>=0)dp[i][j]=add(dp[i][j],mul( (2*j-(i-1) ),dp[i-1][j] ));
            if(j-1>=0)dp[i][j]=add(dp[i][j],dp[i-1][j-1]);
        }
    }

    fact[0]=1;
    for(int i=1;i<maxm;i++)fact[i]=mul(fact[i-1],i);
    inv[maxm-1]=invv(fact[maxm-1]);
    for(int i=maxm-1;i>0;i--)inv[i-1]=mul(inv[i],i);

    int ret=calc_singles();

    int up=1;
    int kk=k;
    for(int r=1;r<m;r++){
        up=mul(up,kk);
        kk--;

        int real_r=m-r;
        ret=sub(ret, mul(fact[r],mul( inv[r] , mul(up,mul( count_beautiful(m-2*r,k-r) , fksum(n-m-real_r,real_r) ) ) )) );
    }
    printf("%d\n",ret);

    return 0;
}