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
#pragma GCC optimize("O3,unroll-loops,inline")
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;

const ll mod = 1e9+7;
ll mul(ll a, ll b){
    return a*b%mod;
}ll modpow(ll a, ll e){
    ll ans = 1;
    while(e){
        if (e&1) ans = mul(ans, a);
        a = mul(a,a);
        e/=2;
    }return ans;
}
void add(ll& a, ll b) {
    a += b;
    a = (a < mod ? a : a - mod);
}
void sub(ll& a, ll b) {
    a -= b;
    a = (a < 0 ? a + mod : a);
}

const int mxN = 1e6+7; 
ll prob[mxN], pref[mxN], preftri[mxN];

ll get(ll* arr, int l, int r) { // [ )
    return ((r > 0 ? arr[r-1] : 0) - (l > 0 ? arr[l-1] : 0) + mod)%mod;
}

map<pair<vi,int>,ll> dp;
ll brute(vi a, int k) {
    sort(all(a));
    if (a[0] <= 0) return 0;
    reverse(all(a));
    if (dp.count({a,k})) return dp[{a,k}];
    ll ans = 0;
    rep(take,1,k+1){
        auto b = a;
        b[0] -= take;
        ans += 1 + brute(b, k);
    }
    return dp[{a,k}] = mul(ans, modpow(k, mod-2));
}
ll super(int n, int m, int k) {
    vi a(n, m);
    return brute(a, k);
}

int main(){
    cin.tie(NULL),ios::sync_with_stdio(false);
    
    int n,k,m; cin >> n >> k >> m;
    ll invk = modpow(k, mod-2);
    
    prob[0] = 1, prob[1] = mod-1;
    rep(i,0,m-1) {
        add(prob[i+1], prob[i]);
        ll nv = mul(prob[i], invk);
        add(prob[i+1], nv);
        if (i+k+1<m) sub(prob[i+k+1], nv);
    }
    memcpy(pref,prob,8*m);
    rep(i,0,m-1) add(pref[i+1], pref[i]);
    memcpy(preftri,prob,8*m);
    rep(i,0,m) preftri[i] = mul(preftri[i], i);
    rep(i,0,m-1) add(preftri[i+1], preftri[i]);

    ll ans = 0;

    rep(i,0,m){
        // minimum is equal to i. How many moves?

        ll prob_win = mul(invk, max(0, i + k + 1 - m));

        // from [..., i) to [i, m) --> min(m-1, j+k) - (i-1) ways for j
        // triangle for [..., m-1-k) and square for [m-1-k, i)
        ll prob_over = 0;
        if (i==0) prob_over = 1; // no prev?
        else {
            int lo = max(0, i-k);
            int mid = max(lo, min(i, m-1-k));

            add(prob_over, get(preftri, lo, mid));
            add(prob_over, mul(get(pref, lo, mid), k - (i-1)));

            add(prob_over, mul(get(pref, mid, i), m - i));
            
            prob_over = mul(prob_over, invk);
        }

        ll prob_over_strict = prob_over;
        sub(prob_over_strict, prob[i]);

        if (prob_win != 0) {
            ll expmoves = modpow(prob_over, n);
            sub(expmoves, modpow((mul(prob[i], mod+1-prob_win) + prob_over_strict)%mod, n));
            expmoves = mul(expmoves, modpow(prob_win, mod-2));
            add(ans, expmoves);
        }else{
            assert(prob_over == 1);
            ll expmoves = mul(n, prob[i]);
            add(ans, expmoves);
        }
    }

    cout << ans << '\n';
    // assert(ans == super(n,m,k));
}