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
// Author : Jakub Rożek
// Task   : KOS - Kostki [A]
// Memory : m
// Time   : m + k * log(MOD)

// Myśle o tym jako prostokąt gracze na sumy – ruch to zamalowanie k pól i wygrywamy jak wyjdziemy poza
// E(ruchy) to ∑ po komurkach : szansa z jaką zrobi krok z tego pola.
// Na tą szanse wpływa: P(znalazłem się na tym polu) * P(gra się nie skonczyła)
// pierwsze można obliczyć w dynamiku łatwo a drugie to:
// gra się nie skończyła wtedy gdy inni gracze swój oststni ruch mają na polu >= s – to też można policzyć w dp
// Tu są 2 opcje kończy > s i kończy = s.  Niech x kończy na s wtedy:
// musimy wybrać kturzy to są npok(n-1, x) i dla każdego uwzględnić szanse z jaką zakończy w s i w >s.
// ci >s nas nie interesują ale z tymi z s musimy walczyć kto wykona ruch i mam na to 1/x+1 szans (jak kto inny wykona to sie skonczy gra)


#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll MOD = 1000000007;
const int N = 1000000;

// ll silnia[N+1];
// ll odwrotna_silnia[N+1];
ll jestem[N+1];         // P(będę mieć tyle punktów, jestem na tym polu)
ll ostatni[N+1];        // P(z tego miejsca koncze)
ll ostatni_ponad[N+1];  // P(z wiekszych koncze)

ll power(ll a, ll b) {
    ll w = 1;
    while (b > 0) {
        if (b & 1) w = w * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return w;
}

// ll npok(ll n, ll k) {
//     ll w = 1;
//     w = (w * silnia[n]) % MOD;
//     w = (w * odwrotna_silnia[n-k]) % MOD;
//     w = (w * odwrotna_silnia[k]) % MOD;
//     return w;
// }

// void policz_silnie(int n) {
//     silnia[0] = 1;
//     for (int i=1; i<=n; ++i) {
//         silnia[i] = (silnia[i-1] * i) % MOD;
//     }
//     odwrotna_silnia[n] = power(silnia[n], MOD-2);
//     for (int i=n; i>0; --i) {
//         odwrotna_silnia[i-1] = (odwrotna_silnia[i] * i) % MOD;
//     }
// }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // policz_silnie(N);

    ll n, k, m;

    cin >> n >> k >> m;

    const ll inv_k = power(k, MOD-2);   // = 1/k

    // licze: jestem[i] = ∑(j=i-k...i-1) jestem[j] / k
    jestem[0] = 1;
    ll suma_ostatnich = 1;
    for (int i=1; i<m; ++i) {
        jestem[i] = suma_ostatnich * inv_k % MOD;
        suma_ostatnich += jestem[i];
        if (i-k >= 0) {
            suma_ostatnich += MOD - jestem[i-k];
        }
        suma_ostatnich %= MOD;
    }

    // licze: ostatni[i] = jestem[i] * max(0, k-m+i+1) / k; ten max to ile krokow da mi >=m
    for (int i=0; i<m; ++i) {
        ostatni[i] = (jestem[i] * max<ll>(0, k-m+i+1)) % MOD;
        ostatni[i] = (ostatni[i] * inv_k) % MOD;
    }

    // licze: ostatni_ponad[i] = ∑(j>i) oststni[j]
    ostatni_ponad[m-1] = 0;
    for (ll i=m-2; i>=0; --i) {
        ostatni_ponad[i] = (ostatni_ponad[i+1] + ostatni[i+1]) % MOD;
    }

    // licze wynik
    ll answer = 0;
    ll a, b;

    // stąd zawsze zrobie ruch
    for (int i=0; i<m-k; ++i) {
        answer = (answer + jestem[i] * n) % MOD;
    }
    // tu zalezy od P(legalny ruch)
    // wynik += ∑(i)∑(x=0..n-1)  jestem[i] * n * npok(n-1,x) * ostatni[i]^x * oststni_ponad[i]^(n-1-x) / x+1
    // już działa ale wolno O(nm)-  można to uproscić
    // npok(n-1,x) * ostatni[i]^x * oststni_ponad[i]^(n-1-x) przypomina wzór (a+b)^n
    // (a+b)^n = ∑(y=0..n) npok(n, y) * a^y * b^n-y
    // musimy się najpierw pozbyć 1/x+1 bo psuje
    // n / x+1 * npok(n-1, x) = npok(n, x+1)
    // wynik += ∑(i)  jestem[i] * ∑(x=0..n-1)  npok(n,x+1) * ostatni[i]^x * oststni_ponad[i]^(n-1-x)
    // teraz zastosujmy wzór: (a+b)^n = ∑(y=0..n) npok(n, y) * a^y * b^n-y
    // gdy y = x+1 to: (a+b)^n = ∑(x=-1..n-1) npok(n,x+1) * a^x+1 * b^n-x-1
    // (a+b)^n = a * ∑(x=-1..n-1) npok(n,x+1) * a^x * b^n-x-1
    // (a+b)^n = a * ( (∑(x=0..n-1) npok(n,x+1) * a^x * b^n-x-1) + (a^-1 * b^n) )
    // (a+b)^n / a - b^n/a = ∑(x=0..n-1) npok(n,x+1) * a^x * b^n-x-1
    // ((a+b)^n - b^n) / a = ∑(x=0..n-1) npok(n,x+1) * a^x * b^n-x-1
    // wynik += ∑(i)  jestem[i] * ((ostatni[i]+oststni_ponad[i])^n - oststni_ponad[i]^n) / ostatni[i]
    for (int i=max(0, (int)(m-k)); i<m; ++i) {
        a = (ostatni[i] + ostatni_ponad[i]) % MOD;
        a = power(a, n);
        b = power(ostatni_ponad[i], n);
        a = (a + MOD - b) % MOD;
        a = (a * power(ostatni[i], MOD-2)) % MOD;
        answer = (answer + jestem[i] * a) % MOD;
    }

    cout << answer << '\n';
}