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
#include <bits/stdc++.h>
using namespace std;
#define fwd(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) fwd(i, 0, n)
#define all(X) X.begin(), X.end()
#define sz(X) int(size(X))
#define pb push_back
#define eb emplace_back
#define st first
#define nd second
using pii = pair<int, int>; using vi = vector<int>;
using ll = long long; using ld = long double;
#ifdef LOC
auto SS = signal(6, [](int) { *(int *)0 = 0; });
#define DTP(x, y) auto operator<<(auto &o, auto a) -> decltype(y, o) { o << "("; x; return o << ")"; }
auto operator<<(auto &o, auto a) -> decltype(all(a), o);
DTP(o << a.st << ", " << a.nd, a.nd);
DTP(for (auto i : a) o << i << ", ", all(a));
#define deb(x...) cerr << setw(4) << __LINE__ << ":[" #x "]: ", [](auto... arg_) { (( cerr << arg_ << ", " ), ...) << '\n'; }(x)
#else
#define deb(...) 0
#endif

const int P = 1e9 + 7, phiP = P - 1;
struct mint {
    int x = 0;
    mint operator+(mint o) const {return {x + o.x >= P ? x + o.x - P : x + o.x}; }
    mint operator-(mint o) const {return {x < o.x ? x - o.x + P : x - o.x}; }
    mint operator+() const {return *this; }
    mint operator-() const {return {x ? P - x : 0}; }
    mint operator*(mint o) const {return {int(ll(x) * o.x % P)}; }
    mint operator/(mint o) const {return *this * o.inv(); }
    mint & operator+=(mint o) {return *this = *this + o; }
    mint & operator-=(mint o) {return *this = *this - o; }
    mint & operator*=(mint o) {return *this = *this * o; }
    mint & operator/=(mint o) {return *this = *this / o; }
    mint pow(ll e) const {
        mint ret{1}, b(*this);
        for (; e; e >>= 1) {
            if (e & 1)
                ret *= b;
            b *= b;
        }
        return ret;
    }
    mint inv() const {return pow(phiP - 1); }
};

auto &operator<<(auto &os, mint m) {
    return os << m.x - (2 * m.x >= P && &os == &cerr ? P : 0);
}

// (x^n-y^n)/(x-y)
mint sym(mint x, mint y, int n) {
    if (n == 0) return {};
    if (x.x != y.x)
        return (x.pow(n) - y.pow(n)) / (x-y);
    return mint{n} * x.pow(n-1);
}

int main() {
    int n, k, m;
    cin >> n >> k >> m; // ppl sides points

    mint invK = mint{k}.inv();

    vector<mint> prefWWays(m);
    prefWWays[0] = mint{1};

    auto sumWWays = [&](int l, int r) {
        return prefWWays[r] - (l ? prefWWays[l-1] : mint{});
    };

    fwd(i, 1, m) {
        mint here = invK * sumWWays(max(i-k, 0), i-1);
        prefWWays[i] = prefWWays[i-1] + here;
    }

    mint ans;

    vector<mint> stBelow(m+1);

    fwd(i, 1, m+1) {
        stBelow[i] = stBelow[i-1];
        // deb(i, sumWWays(i-1, i-1), min(k, m-i));
        stBelow[i] += sumWWays(i-1, i-1) * mint{min(k, m-i)} * invK;
        if (i != 1) stBelow[i] -= sumWWays(max(i-2-(k-1), 0), i-2) * invK;
    }

    rep(y, m) {
        mint a = stBelow[y+1], b = stBelow[y];

        if (!y)
            b += mint{1};

        ans += sym(a, b, n) * sumWWays(y, y);
    }

    cout << ans.x << '\n';
}