1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
using namespace std;
const int N=1e6,P=1e9+7;
static int fac[N+1],fi[N+1];
inline int add(int x,int y){
  int s=x+y; if(s>=P)s-=P; return s;
}
inline void self_add(int &x,int y){
  if((x+=y)>=P)x-=P;
}
inline int qpow(int a,int b){
  int r=1;
  while(b){
    if(b&1)r=1ll*r*a%P;
    a=1ll*a*a%P,b>>=1;
  }
  return r;
}
inline int com(int n,int m){
  return 1ll*fac[n]*fi[m]%P*fi[n-m]%P;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,k,m; cin>>n>>k>>m;
  for(int i=fac[0]=1;i<=n;i++)
    fac[i]=1ll*fac[i-1]*i%P;
  fi[n]=qpow(fac[n],P-2);
  for(int i=n;i;i--)
    fi[i-1]=1ll*fi[i]*i%P;
  int ik=qpow(k,P-2);
  vector<int> e(m+1),se(m+1);
  for(int i=1;i<=m;i++){
    e[i]=add(1ll*add(se[i-1],i-k-1>=0?P-se[i-k-1]:0)*ik%P,1);
    se[i]=add(se[i-1],e[i]);
  }
  if(n==1)cout<<e[m]<<endl;
  else if(k==1)cout<<add(1ll*(m-1)*n%P,1)<<endl;
  else if(max({n,m,k})<=5){
    map<vector<int>,int> mp;
    vector<int> v(n);
    auto dfs=[&](auto &&self,vector<int> v)->int{
      if(v.back()>=m)return 0;
      if(mp.find(v)!=mp.end())return mp[v];
      int e=0;
      for(int i=0,p=0;i<k;i++){
        v[p]++;
        for(int j=1;j<n;j++)
          if(v[j]<v[j-1])swap(v[j],v[j-1]),p=j;
        self_add(e,self(self,v));
      }
      return mp[v]=add(1ll*e*ik%P,1);
    };
    cout<<dfs(dfs,v)<<endl;
  }
  return 0;
}