#include<bits/stdc++.h> #define int long long using namespace std; const int mod=1e9+7; const int maxn=5005; int f[maxn],inv[maxn]; int n,k,m,ans; int qpow(int a,int b) { int ret=1; while(b) { if(b&1) ret=(ret*a)%mod; a=(a*a)%mod; b>>=1; } return ret; } int C(int x,int y) { return (((f[x] * inv[y])%mod) * inv[x-y]) %mod; } signed main() { scanf("%lld%lld%lld",&n,&k,&m); f[0] = 1; inv[0] = 1; for(int i=1;i<=5000;++i) f[i] = (f[i-1] * i) %mod; inv[5000] = qpow(f[5000] , mod-2); for(int i=4999;i>0;--i) inv[i] = qpow(f[i],mod-2); for(int i=n-k+1;i>=1;--i) { int sum1=qpow(i,m); int sum2=C(n-i-1,k-2); //cout<<sum1<<" "<<sum2<<endl; ans = (ans+(sum1*sum2)%mod)%mod; } printf("%lld",ans); }