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
#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <vector>

using namespace std;

const long long M = 1000000007;

// Szybkie potęgowanie modularne
long long power(long long base, long long exp) {
    long long res = 1;
    base %= M;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % M;
        base = (base * base) % M;
        exp /= 2;
    }
    return res;
}

// Odwrotność modularna
long long inverse(long long n) {
    return power(n, M - 2);
}

int main() {
    // Ekstremalnie szybkie operacje I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n, k, m;
    if (!(cin >> n >> k >> m)) return 0;

    // Szybka prekalkulacja odwrotności liczb od 1 do k
    vector<long long> inv(k + 1);
    for (int i = 1; i <= k; i++) {
        if (i == 1) inv[i] = 1;
        else inv[i] = (M - M / i) * inv[M % i] % M;
    }

    vector<long long> p(m);
    p[0] = 1;
    long long sum_p = 1;
    long long inv_k = inverse(k);

    long long Q_prev = 0;
    long long Q_curr = 0;
    long long total_E = 0;

    for (long long c = 0; c < m; c++) {
        // 1. Obliczanie p_c (prawdopodobieństwa wejścia na pole c) przy użyciu przesuwnego okna
        if (c > 0) {
            p[c] = sum_p * inv_k % M;
            sum_p = (sum_p + p[c]) % M;
            if (c >= k) {
                sum_p = (sum_p - p[c - k] + M) % M;
            }
        }

        // 2. Liczba wygrywających oczek na kostce z pola c
        long long W = k - m + c + 1;
        if (W < 0) W = 0;
        if (W > k) W = k; 

        // 3. Prawdopodobieństwo, że gracz kończy na c i wygrywa z niego
        long long alpha = p[c] * W % M * inv_k % M;
        Q_curr = (Q_prev + alpha) % M;

        long long E_c = 0;
        
        // 4. Składowa liczby rzutów wykonanych dokładnie z pola c
        if (W == 0) {
            long long term = power((1 - Q_prev + M) % M, n - 1);
            E_c = (n % M) * p[c] % M * term % M;
        } else {
            long long term1 = power((1 - Q_prev + M) % M, n);
            long long term2 = power((1 - Q_curr + M) % M, n);
            long long diff = (term1 - term2 + M) % M;
            E_c = k * inv[W] % M * diff % M;
        }

        total_E = (total_E + E_c) % M;
        Q_prev = Q_curr;
    }

    // Wypisanie wyniku ułamka w formacie modulo 10^9+7
    cout << total_E << "\n";

    return 0;
}