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

using namespace std;
#define fors(u, n, s) for(int u = (s); u<(n); u++)
#define foru(u, n) fors(u, n, 0)
#define f first
#define s second
#define vec vector
#define pb push_back
#define sz(x) ((int)x.size())
typedef long long ll;

#define debug(x) cout << __LINE__ << " | " << x << endl
// #define debug(x) {}

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

const int MOD = 1e9+7;
struct Modular {
  int value;

  Modular(long long v = 0) { value = v % MOD; if (value < 0) value += MOD;}
  Modular(long long a, long long b) : value(0){ *this += a; *this /= b;}

  Modular& operator+=(Modular const& b) {value += b.value; if (value >= MOD) value -= MOD; return *this;}
  Modular& operator-=(Modular const& b) {value -= b.value; if (value < 0) value += MOD;return *this;}
  Modular& operator*=(Modular const& b) {value = (long long)value * b.value % MOD;return *this;}

  friend Modular mexp(Modular a, long long e) {
    Modular res = 1; while (e) { if (e&1) res *= a; a *= a; e >>= 1; }
    return res;
  }
  friend Modular inverse(Modular a) { return mexp(a, MOD - 2); }

  Modular& operator/=(Modular const& b) { return *this *= inverse(b); }
  friend Modular operator+(Modular a, Modular const b) { return a += b; }
  friend Modular operator-(Modular a, Modular const b) { return a -= b; }
  friend Modular operator-(Modular const a) { return 0 - a; }
  friend Modular operator*(Modular a, Modular const b) { return a *= b; }
  friend Modular operator/(Modular a, Modular const b) { return a /= b; }
  friend std::ostream& operator<<(std::ostream& os, Modular const& a) {return os << a.value;}
  friend bool operator==(Modular const& a, Modular const& b) {return a.value == b.value;}
  friend bool operator!=(Modular const& a, Modular const& b) {return a.value != b.value;}
};

const int N = 1e6+100;;

Modular p[N];
Modular dp[N];

int n, k, m;

void get_p(){
	// vec<Modular> p(m);
	Modular s = 1;
	vec<Modular> upd(m, 0);
	upd[0] = Modular(1);
	if(m > 1) upd[1] = Modular(-1);
	Modular val = 0;
	
	foru(i, m){
		val += upd[i];
		p[i] = val/s;
		Modular delta = val/Modular(k);
		if(i+1 < m) upd[i+1] += delta;
		if(i+k+1 < m) upd[i+k+1] -= delta;
		int overshoot = i+k-(m-1);
		if(overshoot > 0) s -= Modular(overshoot)*delta;
	}

	// return p;
}

void get_dp(){
	// vec<Modular> dp(m, 0);

	dp[m-1] = 1;

	for(int i = m-2; i>=0; i--){
		Modular q = Modular(min(m-1-i, k))/Modular(k);

		Modular h = 1-p[i]+q*p[i];
		Modular pw = mexp(h, n-1);
		Modular prod = n*p[i]*q*pw;

		dp[i] += h*pw*dp[i+1];
		
		if(q == 1) dp[i] += prod;
		else dp[i] += (1-h*pw)/(1-q);
	}
}

void solve() {
	cin >> n >> k >> m;

	get_p();
	get_dp();

	cout << dp[0] << endl;
}

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

	srand(time(NULL));

	solve();

	return 0;
}