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
#include <algorithm>
#include <bitset>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) (int)(x).size()
#define CLEAR(tab) memset(tab, 0, sizeof(tab))
#define REP(x, n) for(int x = 0; x < (n); x++)
#define FOR(x, b, e) for(int x = (b); x <= (e); x++)
#define FORD(x, b, e) for(int x = (b); x >= (e); x--)
#define VAR(v, n) __typeof(n) v = (n)
#define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define DEBUG(fmt, ...) fprintf(stderr, fmt, ##__VA_ARGS__)

typedef long long int LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int MXN = 1000010;
const int C = 262144;
const int INF = 1000000001;
const int MOD = 1000000007;

int n, k, m;
LL a[MXN], pref[MXN];
int kon;

LL pow(LL a, LL b) {
	LL res = 1;
	a %= MOD;

	while(b) {
		if(b % 2)
			res = res * a % MOD;
		a = a * a % MOD;
		b /= 2;
	}

	return res;
}

void test() {
	scanf("%d %d %d", &n, &k, &m);
	if(m > k)
		kon = m - k;
	LL inv_k = pow(k, MOD - 2);
	a[0] = 1;

	LL sum = 0;
	FOR(i, 0, m - 1) {
		if(i)
			a[i] = sum * inv_k % MOD;
		sum = (sum + a[i]) % MOD;
		if(i >= k)
			sum = (sum - a[i - k] + MOD) % MOD;
		pref[i + 1] = (pref[i] + a[i]) % MOD;
	}

	LL res = 0;
	FOR(i, 0, m - 1) {
		if(i < kon)
			res = (res + ((LL)n * a[i]) % MOD) % MOD;
	}

	LL F = 1;
	LL G_sum = 0;
	LL interval_sum_invk = 1;

	FOR(i, 0, min(k, m) - 1) {
		LL pocz = max(kon - k + i, 0);
		if(pocz <= (kon - 1) && kon)
			interval_sum_invk = ((pref[kon] - pref[pocz] + MOD) % MOD) * inv_k % MOD;
		else if(i)
			interval_sum_invk = 0;

		LL g = ((G_sum * inv_k % MOD) + interval_sum_invk) %  MOD;
		G_sum = (G_sum + g) % MOD;

		LL c = (kon + k - m + 1 + i) % MOD;
		LL tmp = ((LL)c * g % MOD) * inv_k % MOD;
		LL F_next = (F - tmp + MOD) % MOD;

		tmp = (((pow(F, n) - pow(F_next, n) + MOD) % MOD) * k % MOD) * pow(c, MOD - 2) % MOD;
		res = (res + tmp) % MOD;

		F = F_next;
	}

	printf("%lld\n", res);
}

int main() {
	int te = 1;
	//scanf("%d", &te);
	while(te--)
		test();
	return 0;
}