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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
#include <bits/stdc++.h>
using namespace std;
template <int P>
class mod_int
{
    using Z = mod_int;

private:
    static int mo(int x) { return x < 0 ? x + P : x; }

public:
    int x;
    int val() const { return x; }
    mod_int() : x(0) {}
    template <class T>
    mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {}
    bool operator==(const Z &rhs) const { return x == rhs.x; }
    bool operator!=(const Z &rhs) const { return x != rhs.x; }
    Z operator-() const { return Z(x ? P - x : 0); }
    Z pow(long long k) const
    {
        Z res = 1, t = *this;
        while (k)
        {
            if (k & 1)
                res *= t;
            if (k >>= 1)
                t *= t;
        }
        return res;
    }
    Z &operator++()
    {
        x < P - 1 ? ++x : x = 0;
        return *this;
    }
    Z &operator--()
    {
        x ? --x : x = P - 1;
        return *this;
    }
    Z operator++(int)
    {
        Z ret = x;
        x < P - 1 ? ++x : x = 0;
        return ret;
    }
    Z operator--(int)
    {
        Z ret = x;
        x ? --x : x = P - 1;
        return ret;
    }
    Z inv() const { return pow(P - 2); }
    Z &operator+=(const Z &rhs)
    {
        (x += rhs.x) >= P && (x -= P);
        return *this;
    }
    Z &operator-=(const Z &rhs)
    {
        (x -= rhs.x) < 0 && (x += P);
        return *this;
    }
    Z operator-() { return -x; }
    Z &operator*=(const Z &rhs)
    {
        x = 1ULL * x * rhs.x % P;
        return *this;
    }
    Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
#define setO(T, o)                                  \
    friend T operator o(const Z &lhs, const Z &rhs) \
    {                                               \
        Z res = lhs;                                \
        return res o## = rhs;                       \
    }
    setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /)
#undef setO
        friend istream &operator>>(istream &is, mod_int &x)
    {
        long long tmp;
        is >> tmp;
        x = tmp;
        return is;
    }
    friend ostream &operator<<(ostream &os, const mod_int &x)
    {
        os << x.val();
        return os;
    }
};
const int P = 1000000007;
using Z = mod_int<P>;
int n, k, m;
const int N = 1000000;
Z f[1000020]; // someone score = i
Z g[1000020]; // someone score > i and < m, from < i
Z fac[1000020];
Z ifac[1000020];
Z inv[1000020];
Z a[1000020];
Z C(int n, int i) { return n < 0 || i < 0 || n < i ? 0 : fac[n] * ifac[i] * ifac[n - i]; }
int main()
{
    fac[0] = 1;
    for (int i = 1; i <= N; i++)
        fac[i] = fac[i - 1] * i;
    ifac[N] = fac[N].inv();
    for (int i = N; i >= 1; i--)
        ifac[i - 1] = ifac[i] * i;
    for (int i = 1; i <= N; i++)
        inv[i] = fac[i - 1] * ifac[i];
    cin >> n >> k >> m;
    {
        f[0] = 1;
        Z sum = 1;
        for (int i = 1; i <= m; i++)
        {
            f[i] = sum * inv[k];
            sum += f[i] - (i >= k ? f[i - k] : 0);
        }
    }
    {
        for (int i = 0; i < m; i++)
        {
            // for (int j = 1; j <= k; j++)
            // {
            //     if (i + j < m)
            //     {
            //         // g[i + 1] += f[i] * inv[k];
            //         // g[i + j] -= f[i] * inv[k];
            //         // for (int x = i + 1; x < i + j; x++)
            //         //     g[x] += f[i] * inv[k];
            //         // for (int x = i + 1; x < i + j; x++)
            //         //     g[x] += f[i] / k;
            //     }
            // }
            int l = i + 1;
            int r = min(i + k, m - 1);
            int cnt = r - l + 1;
            a[l] -= f[i] * inv[k];
            a[r + 1] += f[i] * inv[k];
            g[i + 1] += f[i] * inv[k] * cnt;
        }
        for (int i = 0; i < m; i++)
            a[i] += a[i - 1];
        for (int i = 0; i < m; i++)
            g[i] += a[i];
        for (int i = 0; i < m; i++)
            g[i] += g[i - 1];
    }
    Z ans = 0;
    for (int i = 0; i < m; i++) // all score >= i
    {
        if (i + 1 == m)
        {
            // cout << f[i] << ' ' << g[i] << '\n';
            assert(g[i] == 0);
            /*
            二项式定理
            g[i] = 0。
            */
            // for (int j = 1; j <= n; j++) // j people score = i
            //     ans += C(n, j) * f[i].pow(j) * g[i].pow(n - j);
            ans += f[i].pow(n);
        }
        else
        {
            Z p = i + k < m ? 1 : inv[k] * (m - 1 - i);
            if (p == 1)
            {
                // for (int j = 1; j <= n; j++) // j people score = i
                //     ans += j * C(n, j) * f[i].pow(j) * g[i].pow(n - j);
                /*
                sum j * C(n, j) * A ^ j * B ^ (n - j) = n * A * (A + B) ^ (n - 1)
                考虑组合意义：
                左边是 j 个人选 A，n - j 个人选 B，然后在选 A 的人里找一个代表元
                右边先钦定代表元，然后 j - 1 个人选 A，n - j 个人选 B，这个二项式定理卷起来
                */
                ans += n * f[i] * (f[i] + g[i]).pow(n - 1);
            }
            else
            {
                // for (int j = 1; j <= n; j++) // j people score = i
                //     ans += C(n, j) * f[i].pow(j) * g[i].pow(n - j) * (p.pow(j) - 1) / (p - 1);

                // for (int j = 1; j <= n; j++) // j people score = i
                //     ans += C(n, j) * f[i].pow(j) * g[i].pow(n - j) * p.pow(j) / (p - 1);
                // for (int j = 1; j <= n; j++) // j people score = i
                //     ans -= C(n, j) * f[i].pow(j) * g[i].pow(n - j) / (p - 1);

                /*
                第一个式子可以先分离出来
                变成求：
                sum C(n, j) * A ^ j * B ^ (n - j)
                和
                sum C(n, j) * A ^ j * B ^ (n - j) * p ^ j
                前者二项式定理卷一下。
                后者显然令 A' = Ap 就还是一个二项式定理。
                */
                ans += ((f[i] * p + g[i]).pow(n) - g[i].pow(n)) / (p - 1);
                ans -= ((f[i] + g[i]).pow(n) - g[i].pow(n)) / (p - 1);
            }
        }
    }
    cout << ans << '\n';
    return 0;
}