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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;
const ll MOD = 1000000007LL;

ll pot(ll a, ll e)
{
    ll wyn = 1;
    a %= MOD;

    while (e > 0)
    {
        if (e & 1)
        {
            wyn = wyn * a % MOD;
        }

        a = a * a % MOD;
        e >>= 1;
    }

    return wyn;
}

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

    int n, k, m;
    cin >> n >> k >> m;

    ll odwK = pot(k, MOD - 2);

    vector<ll> P(m, 0);
    vector<ll> pref(m + 1, 0);
    vector<ll> H(m + 1, 0);

    P[0] = 1;
    pref[1] = 1;

    for (int s = 1; s < m; s++)
    {
        int l = max(0, s - k);

        ll suma = pref[s] - pref[l];
        if (suma < 0)
        {
            suma += MOD;
        }


        P[s] = suma * odwK % MOD;
        pref[s + 1] = pref[s] + P[s];

        if (pref[s + 1] >= MOD)
        {
            pref[s + 1] -= MOD;
        }


    }

    for (int s = m - 1; s >= 0; s--)
    {
        int ile = k - m + s + 1;
        ll dod = 0;

        if (ile > 0)
        {
            dod = P[s] * ile % MOD * odwK % MOD;
        }

        H[s] = H[s + 1] + dod;
        if (H[s] >= MOD)
        {
            H[s] -= MOD;
        }
        
    }

    vector<ll> potN(m + 1, 0);
    vector<ll> potNm1(m + 1, 0);

    for (int s = 0; s <= m; s++)
    {
        potN[s] = pot(H[s], n);
        potNm1[s] = pot(H[s], n - 1);
    }

    int a = max(0, m - k);

    ll ans = 0;

    for (int y = 0; y < a; y++)
    {
        ll dod = 1LL * n * P[y] % MOD * potNm1[y + 1] % MOD;
        ans += dod;

        if (ans >= MOD)
        {
            ans -= MOD;
        }
    }

    for (int y = a; y < m; y++)
    {
        int ile = k - m + y + 1;

        ll wsp = 1LL * k * pot(ile, MOD - 2) % MOD;
        ll rozn = potN[y] - potN[y + 1];

        if (rozn < 0)
        {
            rozn += MOD;
        }

        ans = (ans + wsp * rozn) % MOD;
    }

    cout << ans << '\n';
    return 0;
}