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
96
97
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
using i128=__int128_t;
void die(string S){puts(S.c_str());exit(0);}
const ll mod=1e9+7;
ll ksm(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}
int n,k,m;
ll f[1001000];
ll s[1001000];
ll d[1001000],d2[1001000];
ll fact[1001000],rfact[1001000];
ll Binom(int n,int k)
{
	if(k<0||k>n) return 0;
	return fact[n]*rfact[k]%mod*rfact[n-k]%mod;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k>>m;
	fact[0]=1;
	for(int i=1;i<=n;i++) fact[i]=fact[i-1]*i%mod;
	for(int i=0;i<=n;i++) rfact[i]=ksm(fact[i],mod-2);
	ll iv=ksm(k,mod-2);
	f[0]=s[0]=1;
	for(int i=1;i<m;i++)
	{
		if(i<=k)
			f[i]=s[i-1]*iv%mod;
		else
			f[i]=(s[i-1]-s[i-k-1]+mod)*iv%mod;
		s[i]=(s[i-1]+f[i])%mod;
	}
	for(int i=0;i<m-1;i++)
	{
		ll v=f[i]*iv%mod;
		int k2=min(k,m-i-1);
		d[i+1]=(d[i+1]+(k2+i)*v)%mod;
		d[i+k2]=(d[i+k2]+mod-(k2+i)*v%mod)%mod;
		d2[i+1]=(d2[i+1]+(mod-v))%mod;
		d2[i+k2]=(d2[i+k2]+v)%mod;
	}
	for(int i=1;i<m;i++)
	{
		d[i]=(d[i]+d[i-1])%mod;
		d2[i]=(d2[i]+d2[i-1])%mod;
	}
	ll ans=0;
	for(int i=0;i<m;i++)
	{
		ll v=(d[i]+d2[i]*i)%mod;
		ll v2=f[i];
		ll ok=min(k,m-i-1)*iv%mod;
		if(ok==1)
		{
			ll tot=ksm((v2+v)%mod,n-1)*v2%mod*n%mod;
			ans=(ans+tot)%mod;
		}
		else
		{
			ll ivo=ksm(ok+mod-1,mod-2)%mod;
			ll tot=(ksm((v2*ok+v)%mod,n)-ksm((v2+v)%mod,n)+mod)%mod;
			ans=(ans+ivo*tot)%mod;
		}
	}
	cout<<ans<<'\n';
	return 0;
}