//A tree without skin will surely die.
//A man without face will be alive.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
int const N=2e6+10,mod=1e9+7;
int n,m,k,ans,pw[N],ivpw[N],dp[N],gt[2005][2005];
inline int qpow(int a,int b){int res=1;while (b){if (b&1) res*=a,res%=mod;a*=a,a%=mod,b>>=1;}return res;}
inline int A(int n,int m){
    int g=1;
    per(i,n,n-m+1) g*=i,g%=mod;
    return g;
}
#define add(x,y) (x=((x+y>=mod)?(x+y-mod):(x+y)))
inline int D(int n,int t){
    int nw=0,gr=qpow(pw[t]+mod-1,mod-2);
    rep(p,0,t-1){
        int Q=0,ed=(n-p)/t*t+p;
        Q=(pw[t]*ivpw[p]%mod+mod-ivpw[ed])%mod;
        // for (int j=p;j<=ed;j+=t) add(Q,qpow(pw[j],mod-2)%mod);
        add(nw,(mod-pw[p])%mod*Q%mod);
    }
    // rep(i,0,n) add(nw,(mod-pw[i%t])%mod*qpow(pw[i],mod-2)%mod);
    return nw*gr%mod;
}
inline void work(int L,int res){
    // dp[0]=1;
    if (n<=2000 || m<=100){
        int nw=0;
        rep(i,m,n){
            dp[i]=pw[i-m];
            if (L) add(dp[i],mod-dp[i-m+L]);
            add(nw,dp[i]*pw[n-i]%mod);
        }
        return add(ans,nw*res%mod),void();
    }
    // cout<<nw<<" !@#@!#\n";
    int nw=0;
    if (!L){
        rep(i,m,n) add(nw,pw[i-m]*pw[n-i]%mod);
    }else{
        int t=m-L;
        nw=D(n-m,2*t)*pw[n-m]%mod,nw%=mod;
        add(nw,pw[n+2*t-m]*(n-m+1)%mod);
        int gw=0;
        // rep(i,m,n-t){
            // int S=n-i-t;
            // add(gw,
            // (mod-pw[S-S/(2*t)*(2*t)])%mod*pw[i-m]%mod);
        // }
        gw=D(n-m-t,2*t)*pw[n-m-t]%mod;
        // rep(I,0,n-m-t) add(gw,mod-pw[I%(2*t)]*pw[n-I-t-m]%mod);
        add(gw,pw[n-m+t]*(n-t-m+1)%mod);
        nw+=mod-gw,nw%=mod;
        nw*=qpow((pw[2*t]+mod-1)%mod,mod-2),nw%=mod;
    }
    // cout<<nw<<" Aft!\n";
    add(ans,nw*res%mod);
}
inline void solve(){
    cin>>n>>m>>k,gt[0][0]=1;
    rep(L,1,m) rep(co,1,L){
        gt[L][co]=gt[L-1][co-1]*L%mod;
        if (L>1) gt[L][co]+=(L*(L-1)/2)%mod*gt[L-2][co-1]%mod,gt[L][co]%=mod;
    }
    pw[0]=1,ivpw[0]=1;
    rep(i,1,N-1) pw[i]=pw[i-1]*k%mod,ivpw[i]=qpow(pw[i],mod-2);
    int tot=0,la=1;
    rep(co,0,m) tot+=gt[m][co]*la%mod,tot%=mod,la*=k-co,la%=mod,la*=qpow(co+1,mod-2),la%=mod;
    rep(L,1,m/2){
        int res=0,sd=A(k,L),la=1;
        rep(co,0,m-2*L){
            res+=sd*la%mod*gt[m-2*L][co]%mod,res%=mod;
            la*=k-L-co,la%=mod,la*=qpow(co+1,mod-2),la%=mod;
        }
        tot+=mod-res,tot%=mod,work(L,res);
    }
    work(0,tot);
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1;
    // cin>>t;
    while (t--) solve();
    // cerr<<"Time: "<<(double)clock()/CLOCKS_PER_SEC<<" s\n";
    return 0;
}