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
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1'000'000'007;
int mul(int a, int b) {
	return (long long) a * b % MOD;
}
int my_pow(int a, int b) {
	int r = 1;
	while (b) {
		if (b % 2) {
			r = mul(r, a);
		}
		a = mul(a, a);
		b /= 2;
	}
	return r;
}
int my_inv(int a) {
	return my_pow(a, MOD - 2);
}
int my_div(int a, int b) {
	return mul(a, my_inv(b));
}

int main() {
	int n, k, m;
	cin >> n >> k >> m;
	vector<int> p_here(m);
	vector<int> p_die(m);
	p_here[0] = 1;
	int answer = 0;
	int sum = 0;
	const int MEMO_INV_K = my_inv(k);
	for (int i = 0; i < m; i++) {
		if (i) {
			sum = (sum + p_here[i-1]) % MOD;
			if (i - k - 1 >= 0) {
				sum = (sum - p_here[i-k-1] + MOD) % MOD;
			}
			p_here[i] = mul(sum, MEMO_INV_K); // my_div(sum, k);
		}
		p_die[i] = ((i ? p_die[i-1] : 0) + mul(mul(p_here[i], max(0, i + k - m + 1)), MEMO_INV_K)) % MOD;
		
		int A = (i == 0 ? 1 : (MOD + 1 - p_die[i-1]) % MOD);
		int B = (MOD + 1 - p_die[i]) % MOD;
		
		int first = mul(p_here[i], my_pow(A, n - 1));
		int r = my_div(B, A);
		if (r == 1) {
			answer = (answer + mul(first, n)) % MOD;
		}
		else if (r == 0) {
			answer = (answer + first) % MOD;
		}
		else {
			answer = (answer + mul(first, my_div((my_pow(r, n) + MOD - 1) % MOD, (r + MOD - 1) % MOD))) % MOD;
		}
		// for (int x = 1; x <= n; x++) {
			// answer = (answer + first) % MOD;
			// first = mul(first, ratio);
		// }
		// for (int x = 1; x <= n; x++) {
			// answer = (answer + mul(p_here[i], mul(my_pow(A, n - x), my_pow(B, x - 1)))) % MOD;
			// int A = p_here[i];
			// int B = (i == 0 ? 1 : my_pow((MOD+1-p_die[i-1])%MOD, n - x));
			// int C = my_pow((MOD+1-p_die[i])%MOD, x - 1);
			// answer = (answer + mul(mul(A, B), C)) % MOD;
		// }
	}
	cout << answer << endl;
}