#include <bits/stdc++.h> using namespace std; int n,m,k,ans,mod=100000007; int f(int a,int b) { if(b==0) return 1; if(b%2==1) return a*f(a,b-1)%mod; else { long long m=f(a,b/2)%mod; return m*m%mod; } } void dfs(int t,int tot,int cnt,int x) { if(t==k-1) { ans=(ans+tot+f(n-cnt,m))%mod; return; } for(int i=x; i<n-cnt-k; i++) dfs(t+1,(tot+f(i,m))%mod,cnt+i,i); } int main() { cin>>n>>k>>m; dfs(0,0,0,1); cout<<ans%mod; }