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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <cassert>
#include <iostream>

using namespace std;

using ll = long long;

constexpr ll mod = 1'000'000'007;

constexpr ll szpotmod(ll a, ll b) {
	if (b == 0) return 1;
	ll p = szpotmod(a, b / 2);
	p = (p * p) % mod;
	if (b % 2 == 1) p = (p * a) % mod;
	return p;
}

constexpr ll odw(ll a) {
	return szpotmod(a, mod - 2);
}

constexpr ll sumPower(ll a, ll b, ll n) {
	if (a == b) return (n * szpotmod(a, n)) % mod;
	ll dif = (a - b + mod) % mod;
	ll ano = szpotmod(a, n + 1);
	ll bno = szpotmod(b, n + 1);
	return (((ano - bno + mod) % mod) * odw(dif)) % mod;
}

constexpr ll sumPowerWithI(ll a, ll b, ll n) {
	if (a == b) { 
		ll mult = ((((n + 1) * (n + 2)) % mod) * odw(2)) % mod;
		return (mult * szpotmod(a, n)) % mod;
	}
	ll dif = (a - b + mod) % mod;
	ll ano = ((n + 1) * szpotmod(a, n + 1)) % mod;
	ll bno = (b * sumPower(a, b, n)) % mod;
	return (((ano - bno + mod) % mod) * odw(dif)) % mod;
}

constexpr ll max_n = 1'000'100;

ll pexp[max_n], prob[max_n];

ll jmp_over_prob[max_n], jmp_over_pexp[max_n];

ll n, k, m;

ll ExpFromExact(ll p) {
	assert(p + k >= m);

	// cerr << "EFE: " << p << "\n";

	ll lprob = jmp_over_prob[p], lpexp = jmp_over_pexp[p];
	ll rprob, rpexp;
	if (p == 0) {
		rprob = 1;
		rpexp = 0;
	} else {
		rprob = jmp_over_prob[p - 1];
		rpexp = jmp_over_pexp[p - 1];
	}
	ll pcont = (((k + p - m + 1) * odw(k)) % mod);
	ll eprob = (prob[p] * pcont) % mod;
	ll epexp = (pexp[p] * pcont + eprob) % mod;

	// cerr << prob[p] << " " << pexp[p] << " " << eprob << " " << epexp << "\n";

	if (n == 1) return epexp;

	ll left = (((sumPowerWithI(lprob, rprob, n - 2) * eprob) % mod) * lpexp) % mod;
	ll ex = (sumPower(lprob, rprob, n - 1) * epexp) % mod;
	ll right = (((sumPowerWithI(rprob, lprob, n - 2) * eprob) % mod) * rpexp) % mod;

	// cerr << "! lr " << lprob << " " << rprob << "\n";
	// cerr << sumPower(lprob, rprob, n - 2) << "\n";
	// cerr << left << " " << ex << " " << right << "\n";

	ll res = (left + ex + right) % mod;

	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k >> m;

	ll odwk = odw(k);

	pexp[0] = 0;
	prob[0] = 1;

	ll sum_prob = prob[0];
	ll sum_pexp = pexp[0];

	ll sum_prob_weighted = (((sum_prob * odw(k)) % mod) * min(k, m - 1)) % mod;
	ll sum_pexp_weighted = sum_pexp;

	jmp_over_prob[0] = sum_prob_weighted;
	jmp_over_pexp[0] = sum_pexp_weighted + sum_prob_weighted;

	for(int i = 1; i < m; i++) {
		prob[i] = (odwk * sum_prob) % mod;
		pexp[i] = (odwk * sum_pexp + prob[i]) % mod;

		sum_prob_weighted = (sum_prob_weighted - (sum_prob * odwk) % mod + mod) % mod;
		sum_pexp_weighted = (sum_pexp_weighted - (sum_pexp * odwk) % mod + mod) % mod;

		sum_prob_weighted = (sum_prob_weighted + (((prob[i] * odwk) % mod) * min(k, m - i - 1)) % mod) % mod;
		sum_pexp_weighted = (sum_pexp_weighted + (((pexp[i] * odwk) % mod) * min(k, m - i - 1)) % mod) % mod;

		jmp_over_prob[i] = sum_prob_weighted;
		jmp_over_pexp[i] = (sum_pexp_weighted + sum_prob_weighted) % mod;

		sum_prob = (sum_prob + prob[i]) % mod;
		sum_pexp = (sum_pexp + pexp[i]) % mod;
		if (i + 1 - k > 0) {
			sum_prob = (sum_prob - prob[i - k] + mod) % mod;
			sum_pexp = (sum_pexp - pexp[i - k] + mod) % mod;
		}
	}

	ll res = 0;
	for(int i = max(m - k, 0LL); i < m; i++) {
		ll z = ExpFromExact(i);
		// cerr << "i: " << i << " " << z << "\n";
		res = (res + z) % mod;		
	}

	cout << res << "\n";

	// for(int i = 0; i < m; i++) {
		// cout << prob[i] << " " << pexp[i] << " " << jmp_over_prob[i] << " " << jmp_over_pexp[i] << "\n";
	// }

	// cerr << ((3 * odw(8)) % mod) << "\n";
	// cerr << ((3 * odw(16)) % mod) << "\n";
	// cerr << (1 + odw(2) + 30 * odw(64) + 3 * odw(16) + odw(8) + 5 * odw(256)) % mod << "\n";
}