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
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
using namespace std;
ll M=1e9+7;
ll pot(ll a,ll e){
	ll w=1;
	while(e){
		if(e%2){w*=a;w%=M;}
		e/=2;
		a*=a;a%=M;
	}
	return w;
}
ll inw(ll a){return pot(a,M-2);}
int n,m,k,ink;
map<vector<int>,ll>stany;
vector<int>wynik;
ll policz(vector<int>&v){
	if(stany.find(v)!=stany.end()) return stany[v];
	ll wart=1;
	for(int r=1;r<=k;r++){
		if(v[0]+r<m){
			vector<int>nowe=v;
			nowe[0]=v[0]+r;
			int ind=1;while(ind<n&&nowe[ind]<nowe[ind-1]){swap(nowe[ind],nowe[ind-1]);ind++;}
			ll dod=policz(nowe);
			wart=(wart+(dod*ink)%M)%M;
		}
	}
	stany[v]=wart;
	return wart;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>k>>m;
	ink=inw(k);
	wynik.resize(n);
	cout<<policz(wynik)<<'\n';
	return 0;
}