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
MOD = 10**9 + 7

def odwrotnosc_modulo(liczba, modulo):
    return pow(liczba, modulo - 2, modulo)

def oczekiwana_liczba_ruchow_modulo(liczbaoczek, liczbagraczy, limitpunktow):
    n = liczbaoczek
    k = liczbagraczy
    m = limitpunktow

    # dp[i] = oczekiwana liczba ruchów, gdy minimalny wynik wśród graczy to i
    dp = [0] * (m + n + 1)
    pref = [0] * (m + n + 2)  # suma prefiksowa dp

    inv_n = odwrotnosc_modulo(n, MOD)

    # od końca do początku
    for minimalny_wynik in range(m - 1, -1, -1):
        # liczba graczy, którzy mają minimalny wynik
        # w każdej turze losowo jeden z nich rzuca
        suma_nastepnych = 0
        for oczka in range(1, n + 1):
            nastepny_wynik = minimalny_wynik + oczka
            if nastepny_wynik >= m:
                suma_nastepnych += 0
            else:
                suma_nastepnych += dp[nastepny_wynik]
                if suma_nastepnych >= MOD:
                    suma_nastepnych -= MOD

        # teraz uwzględniamy, że w turze rzuca jeden z minimalnych graczy
        dp[minimalny_wynik] = (1 + suma_nastepnych * inv_n) % MOD

        # prefiks do szybszych obliczeń (jeśli chcemy sumę w przyszłości)
        pref[minimalny_wynik] = (dp[minimalny_wynik] + pref[minimalny_wynik + 1]) % MOD

    # wynik: oczekiwana liczba ruchów od początku gry
    # dla k graczy stosujemy potęgę modularną
    wynik = dp[0]
    return wynik

# wczytanie danych wejściowych
liczbaoczek, liczbagraczy, limitpunktow = map(int, input().split())
print(oczekiwana_liczba_ruchow_modulo(liczbaoczek, liczbagraczy, limitpunktow))