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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
#define MOD 1000000007
int N,K,M,dp[1000009],f1[1000009],su[1000009],su2[1000009];
inline int pw(int a,int b) {
	int as=1;
	while(b) {
		if(b&1) as=1ll*as*a%MOD;
		a=1ll*a*a%MOD;
		b>>=1;
	}
	return as;
}
inline int ni(int a) {
	return pw(a,MOD-2);
}
signed main(void) {
	scanf("%d %d %d",&N,&K,&M);
	M--;
	int aa=ni(K);
	dp[0]=1;
	su[0]=1;
	for(int i=1;i<=M;i++) {
		int ll=std::max(0,i-K);
		dp[i]=su[i-1];
		if(ll) dp[i]=(dp[i]+MOD-su[ll-1])%MOD;
//		for(int j=std::max(0,i-K);j<i;j++) {
//			dp[i]=(dp[i]+dp[j])%MOD;
//		}
		dp[i]=1ll*dp[i]*aa%MOD;
		su[i]=(su[i-1]+dp[i])%MOD;
		su2[i]=(su2[i-1]+1ll*i*dp[i])%MOD;
	}
	int as=0;
	for(int i=0;i<=M;i++) {
		int g2=0;
		int ll=std::max(0,i-K),rr=std::min(i,M-K);
		if(ll<=rr) {
			g2=(g2+1ll*su[rr]*(K-i+MOD))%MOD;
			if(ll) g2=(g2+1ll*(MOD-su[ll-1])*(K-i+MOD))%MOD;

			g2=(g2+su2[rr])%MOD;
			if(ll) g2=(g2+(MOD-su2[ll-1]))%MOD;
		}
//		for(int j=std::max(0,i-K);j<=i&&j<=M-K;j++) {
//			g2=(g2+1ll*dp[j]*(j+K-i))%MOD;
//		}
		ll=std::max(std::max(0,i-K),M-K+1),rr=i;
		if(ll<=rr) {
			g2=(g2+1ll*su[rr]*(M-i))%MOD;
			if(ll) g2=(g2+1ll*(MOD-su[ll-1])*(M-i))%MOD;
		}
//		for(int j=std::max(std::max(0,i-K),M-K+1);j<=i;j++) {
//			g2=(g2+1ll*dp[j]*(M-i))%MOD;
//		}
		g2=1ll*g2*aa%MOD;
		f1[i]=g2;
	}
	for(int i=0;i<=M;i++) {
		int a1=dp[i],g1=0,g2=0;
		if(i==0) g2=1;
		else g2=f1[i-1];
		g1=f1[i];
		if(N==1) {
			as=(as+a1)%MOD;
			continue;
		}
/*		for(int j=0;j<i;j++) {
			for(int k=i;k<=j+K&&k<=M;k++) {
				g2=(g2+1ll*dp[j]*aa)%MOD;				
			}
		}*/
		if(g1==0) {
			as=(as+1ll*a1*pw(g2,N-1))%MOD;
			continue;
		}
		if(g2==0) {
			as=(as+1ll*a1*pw(g1,N-1))%MOD;
			continue;
		}
		if(g1==g2) {
			as=(as+1ll*a1*pw(g1,N-1)%MOD*N)%MOD;			
			continue;
		}
		int qq=1ll*g1*ni(g2)%MOD;
		as=(as+1ll*a1*(pw(qq,N)-1)%MOD*ni(qq-1)%MOD*pw(g2,N-1))%MOD;
/*		for(int j=1;j<=N;j++) {
			p1[j]=1ll*p1[j-1]*g1%MOD;
			p2[j]=1ll*p2[j-1]*g2%MOD;
		}
		for(int j=1;j<=N;j++) {
			as=(as+1ll*a1*p1[j-1]%MOD*p2[N-j])%MOD;
		}*/
	}
	printf("%d",as);
}