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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
#include <bits/stdc++.h>
using namespace std;

const int INPUT_MAX = 1000010;

long long expected_into_interval[INPUT_MAX];

long long expected_at_point[INPUT_MAX];
long long exp_point_pref[INPUT_MAX];
long long exp_point_lin_pref[INPUT_MAX];

long long chance_into_interval[INPUT_MAX];

long long chance_at_point[INPUT_MAX];
long long ch_point_pref[INPUT_MAX];
long long ch_point_lin_pref[INPUT_MAX];


const long long MOD_V = 1000000007;

long long MOD_s(long long x) {
	if (x < 0) {
		x += (((-x) / MOD_V) + 1) * MOD_V;
	}
	return x % MOD_V;
}
long long MOD(long long x) {
	assert(x >= 0);
	return x % MOD_V;
}



long long inverse(long long x);

long long poww_unsafe(long long x, long long exp) {
	// If x == 0, exp < 0 something went VERY wrong
	if (exp == 0) {
		return 1;
	}

	long long res = poww_unsafe(x, exp / 2);
	res *= res;
	res = MOD(res);

	if (exp % 2 == 1) {
		res *= x;
		res = MOD(res);
	}
	return res;
}

long long poww(long long x, long long exp) {
	if (exp < 0) {
		return poww_unsafe(inverse(x), -exp);
	}
	else {
		return poww_unsafe(x, exp);
	}
}

long long inverse(long long x) {
	return poww(x, MOD_V - 2);
}

long long sum(long long a, long long max_n) {
	// Calculates the sum of j * a ^ j
	if (a == 1) {
		//cerr << "Weird sum" << endl;
		return MOD(MOD(max_n * (max_n + 1)) * inverse(2));
	}


	return MOD(MOD_s(MOD(max_n * poww(a, max_n + 2)) - MOD((max_n + 1) * poww(a, max_n + 1)) + a) * inverse(MOD((a-1) * (a-1))));
}

long long geom_sum(long long a, long long max_n) {
	// Calculates the sum of a^j, including j = 0
	if (a == 1) {
		//cerr << "Weird geom_sum" << endl;
		return MOD(max_n + 1);
	}
	return MOD((poww(a, max_n + 1) - 1) * inverse(a - 1));
}


int main() {
	std::ios_base::sync_with_stdio(false);

	int player_count, threshold, k;
	cin >> player_count >> k >> threshold;
	long long k_i = inverse(k);

	chance_at_point[0] = 1;
	ch_point_pref[0] = 0;
	ch_point_pref[1] = 1;
	for (int i = 1; i <= threshold; i++) {
		chance_at_point[i] = 0;

		int max_j = i - 1;
		int min_j = max(0, i - k);
		chance_at_point[i] = MOD(MOD_s(ch_point_pref[max_j + 1] - ch_point_pref[min_j]) * k_i);
		ch_point_pref[i+1] = MOD(ch_point_pref[i] + chance_at_point[i]);
	}

	ch_point_lin_pref[0] = 0;
	for (int i = 0; i <= threshold; i++) {
		ch_point_lin_pref[i + 1] = MOD(ch_point_lin_pref[i] + i * chance_at_point[i]);
	}

	exp_point_pref[0] = 0;
	for (int i = 0; i <= threshold; i++) {
		int max_j = i - 1;
		int min_j = max(0, i - k);
		expected_at_point[i] = MOD(MOD_s(exp_point_pref[max_j + 1] - exp_point_pref[min_j] + ch_point_pref[max_j + 1] - ch_point_pref[min_j]) * k_i);
		exp_point_pref[i+1] = MOD(exp_point_pref[i] + expected_at_point[i]);
	}

	exp_point_lin_pref[0] = 0;
	for (int i = 0; i <= threshold; i++) {
		exp_point_lin_pref[i + 1] = MOD(exp_point_lin_pref[i] + i * expected_at_point[i]);
	}



	chance_into_interval[0] = 1;
	for (int i = 1; i <= threshold; i++) {
		chance_into_interval[i] = 0;
		int max_j = i - 1;
		int min_j = max(0, i - k);

		int min_interval_1 = min_j;
		int max_interval_1 = min(max_j, threshold - 1 - k);
		if (max_interval_1 >= min_interval_1) {
			chance_into_interval[i] = MOD(chance_into_interval[i] + MOD(MOD_s(ch_point_pref[max_interval_1 + 1] - ch_point_pref[min_interval_1]) * MOD_s((k - i + 1) * k_i)));
			chance_into_interval[i] = MOD(chance_into_interval[i] + MOD_s(ch_point_lin_pref[max_interval_1 + 1] - ch_point_lin_pref[min_interval_1]) * k_i);
		}

		int min_interval_2 = max(min_j, threshold - k);
		int max_interval_2 = max_j;
		if (max_interval_2 >= min_interval_2) {
			chance_into_interval[i] = MOD(chance_into_interval[i] + MOD_s(ch_point_pref[max_interval_2 + 1] - ch_point_pref[min_interval_2]) * MOD((threshold - i) * k_i));
		}
	}

	for (int i = 0; i <= threshold; i++) {
		// Calc value for interval [i, threshold)
		expected_into_interval[i] = 0;

		int max_j = i - 1;
		int min_j = max(0, i - k);

		int min_interval_1 = min_j;
		int max_interval_1 = min(max_j, threshold - 1 - k);
		if (max_interval_1 >= min_interval_1) {
			expected_into_interval[i] = MOD(expected_into_interval[i] + MOD(MOD_s(exp_point_lin_pref[max_interval_1 + 1] - exp_point_lin_pref[min_interval_1] + ch_point_lin_pref[max_interval_1 + 1] - ch_point_lin_pref[min_interval_1]) * k_i));
			
			expected_into_interval[i] = MOD_s(expected_into_interval[i] + MOD(MOD_s(exp_point_pref[max_interval_1 + 1] - exp_point_pref[min_interval_1] + ch_point_pref[max_interval_1 + 1] - ch_point_pref[min_interval_1]) * k_i) * (k - i + 1));
		}


		int min_interval_2 = max(min_j, threshold - k);
		int max_interval_2 = max_j;
		if (max_interval_2 >= min_interval_2) {
			expected_into_interval[i] = MOD(expected_into_interval[i] + MOD(MOD(MOD_s(exp_point_pref[max_interval_2 + 1] - exp_point_pref[min_interval_2] + ch_point_pref[max_interval_2 + 1] - ch_point_pref[min_interval_2]) * (threshold - i)) * k_i));
		}
	}


	long long result = 0;
	for (int i = threshold - 1; i >= 0 && i + k >= threshold; i--) {
		long long chance_leading_player_succ = MOD(MOD(chance_at_point[i] * (k - threshold + i + 1)) * k_i);
		long long result_add1 = 0;
		long long result_add2 = 0;

		// Low priority part of the sum

		// Maybe need to sepatately handle chance being 0 but I think it is good as is
		//if (chance_into_interval[i] == 0) {
		//	cout << "AAAAAAAA";
		//}
		if (chance_into_interval[i] != 0 && chance_into_interval[i+1] != 0) {
			long long base_mult = MOD(chance_leading_player_succ * MOD(expected_into_interval[i] * poww(chance_into_interval[i], player_count - 2)));
			result = MOD_s(result - base_mult * sum(MOD(chance_into_interval[i+1] * inverse(chance_into_interval[i])), player_count - 1));
			base_mult = MOD(base_mult * (player_count - 1));
			result = MOD(result + base_mult * geom_sum(MOD(chance_into_interval[i+1] * inverse(chance_into_interval[i])), player_count - 1));


			// Seems to be a bug in the high priority stage
			base_mult = MOD(poww(chance_into_interval[i+1], -1) * MOD(poww(chance_into_interval[i], player_count - 1) * MOD(chance_leading_player_succ * expected_into_interval[i+1])));

			result_add1 = MOD(base_mult * sum(MOD(chance_into_interval[i+1] * inverse(chance_into_interval[i])), player_count - 1));



			base_mult = MOD(MOD(expected_at_point[i] * MOD((k - threshold + i + 1) * k_i) + chance_leading_player_succ) * poww(chance_into_interval[i], player_count - 1));
			result = MOD(result + base_mult * geom_sum(MOD(chance_into_interval[i+1] * inverse(chance_into_interval[i])), player_count - 1));

			//long long chanc_for_leading_player = poww(chance_into_interval[i+1], j) * poww(chance_into_interval[i], player_count - 1 - j);
			//result = result + (((expected_at_point[i] * (k - threshold + i + 1) * k_i + chance_leading_player_succ)) * chanc_for_leading_player);
		}
		else {
			//cerr << "Got to weird case\n";
			// Deranged solution but I think it works
			for (int j = 0; j < min(player_count, 4); j++) {
				// consider having j high priority players
				long long chance_for_low_priority = MOD(poww(chance_into_interval[i+1], j) * poww(chance_into_interval[i], player_count - 1 - j - 1));
				long long chance_for_high_priority = MOD(poww(chance_into_interval[i+1], j - 1) * poww(chance_into_interval[i], player_count - 1 - j));
				long long chanc_for_leading_player = MOD(poww(chance_into_interval[i+1], j) * poww(chance_into_interval[i], player_count - 1 - j));


				result = MOD(result + (player_count - 1 - j) * MOD(chance_leading_player_succ * MOD(chance_for_low_priority * expected_into_interval[i])));
				

				result_add1 = MOD(result_add1 + j * MOD(chance_leading_player_succ * MOD(chance_for_high_priority * expected_into_interval[i+1])));
				

				result = MOD(result + MOD((MOD(MOD(expected_at_point[i] * MOD((k - threshold + i + 1) * k_i)) + chance_leading_player_succ)) * chanc_for_leading_player));
			}
			for (int j = max(4, player_count - 4); j < player_count; j++) {
				// consider having j high priority players
				long long chance_for_low_priority = MOD(poww(chance_into_interval[i+1], j) * poww(chance_into_interval[i], player_count - 1 - j - 1));
				long long chance_for_high_priority = MOD(poww(chance_into_interval[i+1], j - 1) * poww(chance_into_interval[i], player_count - 1 - j));
				long long chanc_for_leading_player = MOD(poww(chance_into_interval[i+1], j) * poww(chance_into_interval[i], player_count - 1 - j));


				result = MOD(result + (player_count - 1 - j) * MOD(chance_leading_player_succ * MOD(chance_for_low_priority * expected_into_interval[i])));
				

				result_add1 = MOD(result_add1 + j * MOD(chance_leading_player_succ * MOD(chance_for_high_priority * expected_into_interval[i+1])));
				

				result = MOD(result + MOD((MOD(MOD(expected_at_point[i] * MOD((k - threshold + i + 1) * k_i)) + chance_leading_player_succ)) * chanc_for_leading_player));
			}
		}


		/*for (int j = 0; j < player_count; j++) {
			// consider having j high priority players
			//long long chance_for_low_priority = MOD(poww(chance_into_interval[i+1], j) * poww(chance_into_interval[i], player_count - 1 - j - 1));
			long long chance_for_high_priority = MOD(poww(chance_into_interval[i+1], j - 1) * poww(chance_into_interval[i], player_count - 1 - j));
			long long chanc_for_leading_player = MOD(poww(chance_into_interval[i+1], j) * poww(chance_into_interval[i], player_count - 1 - j));


			//result = MOD(result + (player_count - 1 - j) * MOD(chance_leading_player_succ * MOD(chance_for_low_priority * expected_into_interval[i])));
			

			//result_add2 = MOD(result_add2 + j * MOD(chance_leading_player_succ * MOD(chance_for_high_priority * expected_into_interval[i+1])));
			

			//result = MOD(result + MOD((MOD(MOD(expected_at_point[i] * MOD((k - threshold + i + 1) * k_i)) + chance_leading_player_succ)) * chanc_for_leading_player));
			
		}*/


		result = MOD(result + result_add1);
		//result = MOD(result + result_add2);
	}
	cout << result << "\n";
/*
	cout << "Chance at point:\n";
	for (int i = 0; i <= threshold; i++) {
		cout << chance_at_point[i] << " ";
	}
	cout << "\nExpected at point:\n";
	for (int i = 0; i <= threshold; i++) {
		cout << expected_at_point[i] << " ";
	}
	cout << "\nExpected at interval:\n";
	for (int i = 0; i <= threshold; i++) {
		cout << expected_into_interval[i] << " ";
	}
	cout << "\n";*/

}