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

#define int long long
const int mod = 1e9+7;

int mul(int a, int b){
    return (a*b)%mod;
}

void add(int &a, int b) {
    a += b;
    if (a >= mod) a-=mod;
}

void sub(int &a, int b){
    a -= b;
    if (a < 0) a += mod;
}

int power(int a, int b){
    if (!b) return 1ll;
    int k = power(a, b/2);
    k = mul(k, k);
    if (b&1) k = mul(k, a);
    return k;
}

void solve() {
    int n, k, m; cin >> n >> k >> m;
    vector<int>dp(m + 1), pref(m + 1);
    dp[0] = 1;
    pref[0] = 1;
    int invK = power(k, mod - 2);
    for (int i = 1; i <= m; i++){
        dp[i] = pref[i - 1];
        if (i > k) sub(dp[i], pref[i - k - 1]);
        dp[i] = mul(dp[i], invK);
        pref[i] = pref[i - 1];
        add(pref[i], dp[i]);
    }
    vector<int>win(m + 1), suf(m + 1), pot(m + 1);
    
    for (int i = m - 1; i >= max(0ll, m - k); i--) {
        assert(i + k - m + 1 >= 0);
        win[i] = mul(invK, mul(i + k - m + 1, dp[i]));
        // cerr << win[i] << " ";
    }
    // cerr << endl;
    for (int i = m - 1; i >= 0; i--) {
        suf[i] = suf[i + 1];
        add(suf[i], win[i]);
        pot[i] = power(suf[i], n);
        // cerr << suf[i] << " ";
    }
    // cerr << endl;

    int ans = 0;
    for (int i = 0; i < m - k; i++) {
        add(ans, mul(n, dp[i]));
    }
    // cerr << ans << endl;
    for (int i = max(0ll, m - k); i < m; i++) {
        // int curr = 0;
        // // suf[i] = pbienstwo ze jakis gracz wygra z pola >= i
        // for (int j = 0; j < n; j++) {
        //     // j osob za malo, reszta chce >= i
        //     add(curr, mul(power(suf[i], n - 1 - j), power(suf[i + 1], j)));
        // }
        // // cerr << mul(dp[i], curr) << endl;
        // add(ans, mul(dp[i], curr));       

        int ile = pot[i]; sub(ile, pot[i + 1]);
        // cerr << mul(dp[i], mul(ile, power(win[i], mod - 2))) << endl;
        add(ans, mul(dp[i], mul(ile, power(win[i], mod - 2)))); 
    }
    cout << ans << endl;
}

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

    solve();

    return 0;
}