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

using namespace std;

const long long modul = 1000000007;

long long poetga(long long baza, long long wykl) {
    long long wnik = 1;
    baza %= modul;
    while (wykl > 0) {
        if (wykl % 2 == 1) wnik = (wnik * baza) % modul;
        baza = (baza * baza) % modul;
        wykl /= 2;
    }
    return wnik;
}

long long odwrotk(long long n) {
    return poetga(n, modul - 2);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long garcze, koci, limt;
    if (!(cin >> garcze >> koci >> limt)) return 0;

    long long odw_k = odwrotk(koci);
    vector<long long> prwad(limt);
    prwad[0] = 1;
    long long suma_p = 1;

    for (int poz = 1; poz < limt; poz++) {
        prwad[poz] = (suma_p * odw_k) % modul;
        suma_p = (suma_p + prwad[poz]) % modul;
        if (poz >= koci) {
            suma_p = (suma_p - prwad[poz - koci] + modul) % modul;
        }
    }

    vector<long long> szns_suk(limt + 1, 0);
    vector<long long> szns_kon(limt, 0);

    for (int krk = limt - 1; krk >= 0; krk--) {
        long long wrt = krk + koci - limt + 1;
        if (wrt < 0) wrt = 0;
        if (wrt > koci) wrt = koci;

        szns_kon[krk] = (wrt * odw_k) % modul;
        long long szns_t = (prwad[krk] * szns_kon[krk]) % modul;
        szns_suk[krk] = (szns_suk[krk + 1] + szns_t) % modul;
    }

    long long oczek = 0;
    for (int mjs = 0; mjs < limt; mjs++) {
        long long wrt = mjs + koci - limt + 1;

        if (wrt <= 0) {
            long long czesc = (garcze * prwad[mjs]) % modul;
            czesc = (czesc * poetga(szns_suk[mjs], garcze - 1)) % modul;
            oczek = (oczek + czesc) % modul;
        }
        else {
            long long czesc = (poetga(szns_suk[mjs], garcze) - poetga(szns_suk[mjs + 1], garcze) + modul) % modul;
            long long odw_q = odwrotk(szns_kon[mjs]);
            czesc = (czesc * odw_q) % modul;
            oczek = (oczek + czesc) % modul;
        }
    }

    cout << oczek << "\n";
    return 0;
}