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
#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define int long long
#define ld long double
#define pb push_back

using namespace std;
#define rg ranges

constexpr int mod = 1e9 + 7;
#define frac pair<int, int>
#define den second
#define num first

int n, m, k;

struct cmp {
    bool operator()(pair<int, vector<int>> a, pair<int, vector<int>> b) const {
        return a.first > b.first;
    }
};

frac operator+(frac a, frac b) {
    a.num = a.num * b.den + b.num * a.den;
    a.den *= b.den;
    a.num %= mod;
    a.den %= mod;
    return a;
}

frac operator*(int a, frac b) {
    b.num *= a;
    b.num %= mod;
    return b;
}

int fastPow(int a, int x) {
    if(!x) return 1;
    auto h = fastPow(a, x / 2);
    h = h * h % mod;
    if(x & 1) h = h * a % mod;
    return h;
}

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> k >> m;
    priority_queue<pair<int, vector<int>>, vector<pair<int, vector<int>>>, cmp> q;
    vector<int> st(n);
    rep(i, 0, n) st[i] = 0;
    q.push({0, st});
    map<vector<int>, map<int, frac>> probs;
    probs[st][0] = {1, 1};
    map<int, frac> probEnd;
    while(q.size()) {
        auto [sum, arr] = q.top();
        auto myP = probs[arr];
        q.pop();
        DEBUG {
            repIn(i, arr) DC << i << ' ';
            DC << ":\n";
            repIn2(mv, p, myP) DC << " " << mv << " " << p.num << "/" << p.den << '\n';
            DC << eol;
        }
        if(arr[n - 1] >= m) {
            repIn2(mv, p, myP) probEnd[mv] = (probEnd.count(mv) ? probEnd[mv] : frac{0, 1}) + p;
            continue;
        }
        int chg = 0;
        rep(i, 1, k + 1) {
            while(chg < n - 1 && arr[chg] + i > arr[chg + 1]) swap(arr[chg], arr[chg + 1]), chg++;
            arr[chg] += i;
            if(arr[0] == 0 && arr[1] == 4) 
                DC << "xd";
            if(probs[arr].empty()) q.push({sum + i, arr});
            repIn2(mv, p, myP) probs[arr][mv + 1] = (probs[arr].count(mv + 1) ? probs[arr][mv + 1] : frac{0, 1}) + frac{p.num, p.den * k % mod};
            arr[chg] -= i;
        }
    }
    frac ans = {0, 1};
    repIn2(mv, p, probEnd) ans = ans + mv * p;
    cout << ans.num * fastPow(ans.den, mod - 2) % mod << '\n';
}