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
#include<bits/stdc++.h>
using namespace std;
long long M=1000000007;
long long bp(long long b,long long e){
	long long r=1;
	while(e){
		if(e&1)r=r*b%M;
		b=b*b%M;
		e>>=1;
	}
	return r;
}
long long mi(long long n){return bp(n,M-2);}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	long long n,k,m;
	cin>>n>>k>>m;
	vector<long long>f(m);
	f[0]=1;
	long long sf=1,ik=mi(k);
	for(int v=1;v<m;++v){
		f[v]=sf*ik%M;
		sf=(sf+f[v])%M;
		if(v>=k)sf=(sf-f[v-k]+M)%M;
	}
	long long pl=0,ans=0;
	for(int v=0;v<m;++v){
		long long B=(1-pl+M)%M,A,x,pv;
		if(v>=m-k){
			x=v+k-m+1;
			pv=x*ik%M;
			pl=(pl+f[v]*pv)%M;
		}
		A=(1-pl+M)%M;
		if(v<m-k)ans=(ans+n*f[v])%M;
		else ans=(ans+(bp(B,n)-bp(A,n)+M)%M*mi(pv))%M;
	}
	cout<<ans<<'\n';
	return 0;
}