#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int INFM=2e3+5;
const int INFN=1e6+5;
const int Mod=1e9+7;
bool vis[INFM];
int n,m,k,fav[INFN],L[INFM],R[INFM],ifav[INFN],f[INFM][INFM],B[INFM][INFM];
int ksm(int x,int y) {
    int ba=x%Mod,ans=1;
    while (y) {
        if (y&1) ans=(ans*ba)%Mod;
        ba=(ba*ba)%Mod;y>>=1;
    }
    return ans;
}
void init() {
    int N=1e6;fav[0]=1;
    for (int i=1;i<=N;i++) fav[i]=fav[i-1]*i%Mod;
    ifav[N]=ksm(fav[N],Mod-2);
    for (int i=N-1;~i;i--) ifav[i]=ifav[i+1]*(i+1)%Mod;
}
int C(int x,int y) {
    if (x<y) return 0;
    return fav[x]*ifav[y]%Mod*ifav[x-y]%Mod;
}
int calc(int x,int y) {
    return (ksm(x,y+1)-1)*ksm(x-1,Mod-2)%Mod;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;init();int res=0;
    for (int i=0;i<=m+3;i++)
        for (int j=0;j<=m+3;j++)
            f[i][j]=0;
    f[0][0]=1;
    for (int i=0;i<m;i++)
        for (int j=0;j<=i;j++) {
            f[i+1][j+1]+=f[i][j]*(k-j-(i-j)/2);
            if (j) f[i+1][j-1]+=f[i][j]*j;
            f[i+1][j+1]%=Mod;
            if (j) f[i+1][j-1]%=Mod;
        }
    int sum=0;
    for (int j=0;j<=m;j++) sum+=f[m][j],sum%=Mod;
    for (int i=1;i<=n;i++) {
        if (i+m-1>n) continue;
        res+=sum*ksm(k,n-m)%Mod;res%=Mod;
    }
    for (int j=0;j<=m;j++) {
        B[j][0]=1;
        int ba=k-j-(m-j)/2+1;
        for (int u=1;u<=m;u++)
            B[j][u]=B[j][u-1]*ba%Mod,ba++;
    }
    int res2=0,invk=ksm(k,Mod-2);
    for (int b=1;b<=m/2;b++) {
        // b  ... b
        int sum=0;
        for (int j=0;j<=m-b*2;j++) {
            // if (k-j-(m-b*2-j)/2<b) continue;
            // int cnt3=1;
            // for (int q=k-j-(m-b*2-j)/2;q>=k-j-(m-b*2-j)/2-b+1;q--) cnt3*=q,cnt3%=Mod;
            // for (int q=1;q<=b;q++) cnt3*=ifav[q]*fav[q-1]%Mod,cnt3%=Mod;
            sum+=f[m-b*2][j]*B[j][b]%Mod;
            sum%=Mod;
        }
        int A=ksm(invk*invk%Mod,m-b),L7=ksm(invk,m-b),invA=ksm(A-1,Mod-2),S3=0,L6=ksm(invk,b);
        L6*=sum;L6%=Mod;
        for (int i=1;i<=m;i++) {
            int cnt=1;
            // m-b
            if (i-1<m-b) cnt*=1,cnt%=Mod;
            else cnt*=1-L7,cnt%=Mod;
            // (m-b)*j<=n-b-i+1
            int li=(n-b-i+1)/(m-b),S2=0;
            if (A==1) S2-=li/2,S2%=Mod;
            else S2=-(ksm(A,li/2+1)-A)*invA%Mod;
            S2*=cnt;S2%=Mod;
            S2*=L6;S2%=Mod;
            res2+=S2;res2%=Mod;
        }
        if (m+1<=n-b+1) {
            for (int k=0;k<m;k++) vis[k]=0;
            for (int i=m+1;i<=n-b+1;i++) {
                if (vis[(n-b-i+1)%(m-b)]) break;
                vis[(n-b-i+1)%(m-b)]=1;L[(n-b-i+1)%(m-b)]=(n-b-i+1);
            }
            for (int k=0;k<m;k++) vis[k]=0;
            for (int i=n-b+1;i>=m+1;i--) {
                if (vis[(n-b-i+1)%(m-b)]) break;
                vis[(n-b-i+1)%(m-b)]=1;R[(n-b-i+1)%(m-b)]=(n-b-i+1);
            }
            for (int i=0;i<m-b;i++) {
                if (!vis[i]) continue;
                int S2=0;
                int ll=R[i]/(m-b),rr=L[i]/(m-b);
                if (ll>rr) continue;
                if (ll==rr) {
                    if (A==1) {
                        for (int li=ll;li<=rr;li++) 
                            S2-=li/2,S2%=Mod;
                    } else {
                        for (int li=ll;li<=rr;li++) 
                            S2+=-ksm(A,li/2+1),S2%=Mod;
                        S2*=invA%Mod;S2%=Mod;
                        S2+=A*invA%Mod*(rr-ll+1)%Mod;S2%=Mod;
                    }
                    S3+=S2;S3%=Mod;
                    continue;
                }
                if (A==1) {

                    int L=ll,R=rr;
                    if (ll&1) S2+=-ll/2,S2%=Mod,ll++;
                    if (rr%2==0) S2+=-rr/2,S2%=Mod,rr--;
                    S2-=(ll/2+rr/2)*(rr/2-ll/2+1);S2%=Mod;
                    // for (int li=ll/2;li<=rr/2;li++) 
                    //     S2-=li*2,S2%=Mod;
                } else {
                    int L=ll,R=rr;
                    if (ll&1) S2+=-ksm(A,ll/2),S2%=Mod,ll++;
                    if (rr%2==0) S2+=-ksm(A,rr/2),S2%=Mod,rr--;
                    S2+=-(calc(A,rr/2)-calc(A,ll/2-1))*2;
                    // for (int li=ll/2;li<=rr/2;li++) 
                    //     S2+=-ksm(A,li)*2,S2%=Mod;
                    ll=L;rr=R;
                    S2*=invA*A%Mod;S2%=Mod;
                    S2+=A*invA%Mod*(rr-ll+1)%Mod;S2%=Mod;
                }
                S3+=S2;S3%=Mod;
            }
            S3*=(invk-ksm(invk,1+(m-b)));S3%=Mod;
            S3*=sum;S3%=Mod;S3*=ksm(invk,b-1);S3%=Mod;
            res2+=S3;res2%=Mod;
        }
    }
    res2*=ksm(k,n);res2%=Mod;res2+=Mod;res2%=Mod;
    res+=res2;res%=Mod;
    res+=Mod;res%=Mod;
    cout<<res<<"\n";
    return 0;
}