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
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#define pr pair
#define f first
#define s second
#define ll long long
#define mp make_pair
#define pll pr<ll,ll>
#define pii pr<int,int>
#define piii pr<int,pii>
using namespace std;
const ll m=1e9+7;
ll pw(ll a,ll b=m-2)
{
	ll r=1;
	while(b)
	{
		if(b&1) r=r*a%m;
		a=a*a%m;
		b>>=1;
	}
	return r;
}
ll ps[1000006],pv[1000006];
ll ed[1000006],ev[1000006];
ll clc(ll n,ll a,ll b,ll ia)
{
	if(n<0) return 0;
	if(a==0||b==0) return pw(a+b,n);
	if(a==b) return pw(a,n)*(n+1)%m;
	b=b*ia%m;
	return pw(a,n)*(pw(b,n+1)+m-1)%m*pw(b+m-1)%m;
}
ll clc2(ll n,ll a,ll b,ll ib)
{
	if(n<0) return 0;
	if(a==0) return pw(b,n);
	if(b==0) return pw(a,n)*(n+1)%m;
	if(a==b) return (n+1)*(n+2)/2%m*pw(a,n)%m;
	a=a*ib%m;
	return ((n+1)*pw(a,n+1)%m+m-clc(n,1,a,1))*pw(a+m-1)%m*pw(b,n)%m;
}
int main()
{
	ios_base::sync_with_stdio(0);
	int n,k,p;
	cin>>p>>k>>n;
	ll as=1,av=0;
	ll ik=pw(k);
	ed[0]=1;
	ed[1]=m-1;
	ll ans=0;
	for(int i=0;i<n;i++)
	{
		if(i) ps[i]=ps[i-1];
		if(i) pv[i]=pv[i-1];
		ps[i]=(ps[i]+ed[i])%m;
		pv[i]=(pv[i]+ev[i])%m;
		if(i+k<n)
		{
			ed[i+k+1]=m-ps[i]*ik%m;
			ev[i+k+1]=m-(pv[i]+ps[i])*ik%m;
			ed[i+1]+=ps[i]*ik%m;
			ev[i+1]+=(pv[i]+ps[i])*ik%m;
			av=(av+ps[i])%m;
		}
		else
		{
			ll cs=ps[i]*(i+k-n+1)%m*ik%m;
			ll cv=(pv[i]+ps[i])*(i+k-n+1)%m*ik%m;
			ll bs=(as+m-cs)%m;
			ll bv=(av+m-cv+ps[i])%m;
			ll ia=pw(as);
			ans+=av*p%m*clc(p-2,as,bs,ia)%m*cs%m;
			ans+=(bv+m-av)*clc2(p-2,bs,as,ia)%m*cs%m;
			ans+=cv*clc(p-1,as,bs,ia)%m;
			ed[i+1]+=ps[i]*ik%m;
			ev[i+1]+=(pv[i]+ps[i])*ik%m;
			as=bs;
			av=bv;
		}
	}
	cout<<ans%m<<endl;
	return 0;
}