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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
#pragma GCC target ("avx2,fma")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define ROF(i,r,l) for(int i=(r);i>=(l);i--)
using namespace std;
int inf=1000000007;
ll infl=1000000000000000007;
const ll mod=1000000007;

#ifdef LOCAL
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

const int N=1000007;

ll pot(ll x,ll p) {ll res=1;for(;p;p>>=1) {if(p&1) res=res*x%mod; x=x*x%mod;} return res;}

ll P[N],E[N],Tp[N],Te[N];

ll Pa[N],Pb[N],Pc[N];
ll Ea[N],Eb[N],Ec[N];

ll ia,pa;

ll G(ll a,ll n)
{
	if(a==1) return n;
	return (1-pa+mod)*ia%mod;
}
ll Gi(ll a,ll n)
{
	if(a==1) return (n*(n-1)/2)%mod;
	ll A=pa;
	ll X=(a-n*A%mod+mod+(n-1)*A%mod*a)%mod;
	ll R=(1-a+mod)%mod;
	return X*ia%mod*ia%mod;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,k;
    cin>>n>>k>>m;
    ll ki=pot(k,mod-2),Sp=1,Se=0;
    P[0]=1;
    Pc[0]=1;
    FOR(i,0,m-1)
    {
		P[i]+=Tp[i],E[i]+=Te[i];
		if(i+k>=m)
		{
			Pb[i]=P[i]*(i+k-m+1)%mod*ki%mod;
			Eb[i]=(E[i]+P[i])*(i+k-m+1)%mod*ki%mod;
		}
		Sp=(Sp-P[i]+mod)%mod;
		Se=(Se-E[i]+mod)%mod;
		ll X=P[i]*ki%mod;
		Sp=(Sp+X*min(k,m-1-i))%mod;
		Tp[i+1]+=X;
		if(Tp[i+1]>=mod) Tp[i+1]-=mod;
		if(i+k+1<m)
		{
			Tp[i+k+1]+=mod-X;
			if(Tp[i+k+1]>=mod) Tp[i+k+1]-=mod;
		}
		X=(E[i]+P[i])*ki%mod;
		Se=(Se+X*min(k,m-1-i))%mod;
		Te[i+1]+=X;
		if(Te[i+1]>=mod) Te[i+1]-=mod;
		if(i+k+1<m)
		{
			Te[i+k+1]+=mod-X;
			if(Te[i+k+1]>=mod) Te[i+k+1]-=mod;
		}
		Pc[i+1]=Sp,Ec[i+1]=Se;
		Pa[i]=Sp,Ea[i]=Se;
		Tp[i+1]+=Tp[i];
		if(Tp[i+1]>=mod) Tp[i+1]-=mod;
		Te[i+1]+=Te[i];
		if(Te[i+1]>=mod) Te[i+1]-=mod;
	}
	ll ans=0;
	FOR(t,0,m-1)
	{
		Ea[t]=Ea[t]*pot(Pa[t],mod-2)%mod;
		Eb[t]=Eb[t]*pot(Pb[t],mod-2)%mod;
		ll ic=pot(Pc[t],mod-2);
		Ec[t]=Ec[t]*ic%mod;
		ll a=Pa[t]*ic%mod,F=pot(Pc[t],n-1);
		ia=pot((1-a+mod)%mod,mod-2),pa=pot(a,n);
		ll X1=F*Pb[t]%mod*G(a,n)%mod;
		ll Y1=(Eb[t]+(n-1)*Ec[t])%mod;
		ll X2=F*Pb[t]%mod*Gi(a,n)%mod;
		ll Y2=Ea[t]-Ec[t]+mod;
		ans=(ans+X1*Y1+X2*Y2)%mod;
	}
	cout<<ans<<endl;
    
    return 0;
}