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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1'000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1'000'000'007LL;
const int N = 1'000'007;
ll sum[N], ils[N], ev[N];
ll sum2[N], ils2[N], ev2[N];

ll QP(ll a, ll n)
{
    ll ans = 1LL;
    while(n > 0LL)
    {
        if(n % 2LL == 1LL)
            ans = (ans * a) % M;
        a = (a * a) % M;
        n /= 2LL;
    }
    return ans;
}

ll C1(ll a, ll b, ll n)
{
    if(a == b)
        return (QP(a, n) * (ll)(n + 1)) % M;
    ll ans = (QP(a, n + 1) - QP(b, n + 1) + M) % M;
    ans *= QP((a-b + M) % M, M - 2LL); ans %= M;

    return ans;
}

ll C2(ll a, ll b, ll n)
{
    if(a == b)
    {
        return (QP(a, n) * (((n * (n + 1)) / 2LL) % M)) % M;
    }
    ll h = QP(a, n);
    ll p1 = (((n * h) % M) * a) % M;
    ll p2 = ((((ll)(n + 1) * h) % M) * b) % M;
    ll p3 = QP(b, n + 1);
    ll ans = (p1 - p2 + p3 + M) % M;
    ans = (ans * a) % M;
    ll h2 = ((a - b) * (a - b)) % M;
    ans = (ans * QP(h2, M - 2LL)) % M;


    // ll xd = 0LL;
    // for(int i = 0; i <= n; ++i)
    // {
    //     xd += (ll)i * ((QP(a, i) * QP(b, n - i))% M);
    //     xd %= M;
    // }

    // cout << "C2: " << a << " " << b << " : " << ans << " " << xd << "\n";

    return ans;
}

void Solve()
{
    int n, k, m;
    cin >> n >> k >> m;

    ll odk = QP(k, M - 2LL);

    ils[0] = 128LL;
    ll as = 0LL, ail = (ils[0] * odk) % M;
    ll as2 = 0LL, ail2 = ((ll)min(k, m - 1) * ail) % M;
    ils2[0] = ils[0];
    for(int i = 1; i <= m; ++i)
    {
        sum[i] = (as + ail) % M;
        ils[i] = ail;
        ev[i] = (sum[i] * QP(ils[i], M - 2LL)) % M;

        sum2[i] = (as2 + ail2) % M;
        ils2[i] = (ail2);
        ev2[i] = (sum2[i] * QP(ils2[i], M - 2LL)) % M;

        as2 = (as2 - as + M) % M;
        ail2 = (ail2 - ail + M) % M;
        as2 += (((ll)sum[i] * (ll)min(k, m - i - 1)) % M) * odk;
        ail2 += (((ll)ils[i] * (ll)min(k, m - i - 1)) % M) * odk;
        as2 %= M; ail2 %= M;


        // cout << "C: " << i << " : " << sum[i] << " " << ils[i] << "\n";
        // cout << "C22: " << i << " : " << sum2[i] << " " << ils2[i] << "\n";

        as = (as + (sum[i] * odk)) % M;
        ail = (ail + (ils[i] * odk)) % M;
        if(i >= k)
        {
            as = (as - (sum[i - k] * odk)) % M;
            ail = (ail - (ils[i - k] * odk)) % M;
            as = (as + M) % M;
            ail = (ail + M) % M;
        }
    }
    ll anss = 0LL, ansil = 0LL;
    for(int i = max(0, m - k); i < m; ++i)
    {
        ll d = (i - (m - k) + 1);
        ll h = ((ils[i] * d) % M) * odk; h %= M;
        ll dil = h;
        dil = (dil * C1(ils2[i], ils2[i + 1], n - 1)) % M;
        ansil += dil;

        ll dsum = 0LL;
        h %= M;
        dsum += ev2[i] * C2(ils2[i], ils2[i + 1], n - 1);
        dsum += ev2[i + 1] * C2(ils2[i + 1], ils2[i], n - 1);
        dsum %= M;
        dsum += C1(ils2[i], ils2[i + 1], n - 1) * ev[i];
        dsum %= M;
        dsum = (dsum * h) % M;
        anss += dsum;

        // for(int j = 0; j <= n - 1; ++j)
        // {
        //     ll as = (ll)j * ev2[i] + (ll)(n - 1 - j) * ev2[i + 1] + ev[i];
        //     ll ail = (ils[i] * d) % M;
        //     ail = (ail * odk) % M;
        //     ail = (ail * QP(ils2[i], j)) % M;
        //     ail = (ail * QP(ils2[i + 1], n - 1 -j)) % M;
        //     // for(int k = 0; k < j; ++k)
        //     //     ail = (ail * ils2[i]) % M;
        //     // for(int k = j; k < n - 1; ++k)
        //     //     ail = (ail * ils2[i + 1]) % M;

        //     as %= M;
        //     as = (as * ail) % M;

        //     // cout << "C: " << i << " " << as << " " << ail << "\n";

        //     // anss += as;
        // }
    }
    anss %= M; ansil %= M;
    ll res = anss * QP(ansil, M - 2LL);
    // cout << "A: " << anss << " " << ansil << "\n";
    ++res; res %= M;
    cout << res << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}